











              Prima ediie (Prave - Bulgaria), mai 1989 

              Este ediia inaugural[, la care echipa Romniei nu a participat. Concursul
a constat dintr-o singur[ prob[, de 4 ore. Juriul a avut la dispoziie ase probleme,
din care a selectat una. S-au pus bazele regulamentului general de concurs, care va
fi definitivat la urm[toarele dou[ ntlniri i constituie cadrul general pentru toate
concursurile informatice pentru elevi.


              IOI. 1 (Selecie). Se consider[ 2*N c[sue situate pe aceeai linie. Dou[
c[sue adiacente sunt goale, N-1 c[sue conin caracterul A iar celelalte N-1
c[sue conin caracterul B. O mutare const[ n interschimbarea coninutului a dou[
c[sue adiacente nevide cu cele dou[ c[sue libere. La intrare este dat[
configuraia iniial[. Se cere:
              1. S[ se efectueze mut[ri succesive, o mutare fiind determinat[ de poziia
primei c[sue nevide dintre cele dou[ adiacente ce particip[ la interschimbare
(aceste c[sue sunt citite de la intrare);
              2. S[ se determine un ir de mut[ri prin care s[ se ajung[ n configuraia
final[ (cea n care toate caracterele A apar naintea caracterelor B, poziia c[suelor
goale putnd fi oarecare);
              3. S[ se ajung[ n configuraia final[ cu un num[r minim de mut[ri. (GI
2/1991)


              Ediia a II-a (Minsk - Bielorusia), iunie 1990

              Incepnd cu aceast[ ediie concursul se desf[oar[ n dou[ runde a cte
5 ore fiecare.
              Deocamdat[ fiecare rund[ const[ n rezolvarea unei singure probleme
selectate de juriu n ziua concursului.


                         IOI. 2 (Joc p[tratic). Se d[ o matrice 4x4 ale c[rei celule conin (n
mod normal) numerele de la 1 la 14, cu excepia a dou[ dintre ele care conin 0
(sunt libere).
Exemplu:
              Matricea A                                         Matricea B

                7  3  5 14                                        1  2  3  4
                0  4  9 13                                        5  6  7  8
                1  0  2 10                                        9 10 11 12
               11  8 12  6                                       13 14  0  0

              Pentru trecerea de la matricea A, citit[ de la intrare, la matricea final[ B se
folosete urm[toarea regul[ de transformare: orice num[r pozitiv poate fi deplasat
orizontal sau vertical (dar nu pe diagonal[) ntr-o celul[ liber[ al[turat[, celula
care a coninut acest num[r devenind liber[.
Se cer:
              1. Introducerea i validarea datelor de intrare;
              2. Vizualizarea unui ir de transform[ri care realizeaz[ trecerea de la o
matrice A citit[ la intrare la matricea final[ B, pentru fiecare transformare trebuind
s[ apar[ num[rul ei de ordine, matricea de la care s-a plecat i matricea la care s-a
ajuns;
              3. S[ se minimizeze num[rul de transform[ri. (GI. 1/1992)


              IOI. 3 (Programare). Pe un interval de timp [0,Endtime] dat, trebuie
asigurat[ paza unei galerii de art[ de c[tre N paznici, fiecare paznic i (1iN)
fiind programat pentru un interval [T1(i),T2(i)] dat. Prin schem[ de gard[
nelegem ansamblul format din vectorii T1 i T2. Timpul este dat n minute. Se
cere:
              1. S[ se verifice dac[ exist[ cel puin doi paznici n orice moment de timp
din intervalul considerat. In caz negativ:
              2. S[ se determine toate perioadele pentru care condiia de mai sus nu este
ndeplinit[;
              3. Fiind dat num[rul natural Length, s[ se determine num[rul minim de
paznici suplimentari angajai pentru cte Length minute, necesari pentru a satisface
condiia cerut[;
              4. S[ se determine dac[ schema de gard[ iniial[ poate fi modificat[
pentru a satisface condiia dat[, permindu-se schimbarea nceputului de gard[ a
paznicilor, dar nu i a lunginii acestei perioade; n caz afrmativ, se cere s[ se listeze
o nou[ schem[ de gard[, care n plus s[ fie obinut[ din cea iniial[ cu un num[r
minim de modific[ri. (Idem).
 
                         Ediia a III-a (Atena - Grecia), iunie 1991

              IOI. 4 (Completare tablou). Se construiete o matrice 5x5 coninnd
toate numerele de la 1 pn[ la 25 astfel:
- poziia pe care este plasat 1 este citit[ de la intrare;
- dac[ i(0i25) este plasat pe poziia de coordonate (x,y) atunci num[rul
i+1 poate fi plasat numai pe una din urm[toarele poziii:
              (x+3,y); (x-3,y); (x,y+3); (x,y-3);
               (x+2,y+2); (x+2,y-2); (x-2,y+2); (x-2,y-2)
f[r[ a iei nafara matricii.
(A) Fiind date la intrare coordonatele poziiei n care apare 1, s[ se produc[ la
ieire o matrice construit[ conform regulilor de mai sus cu respectarea ncadr[rii
n chenarul din figura urm[toare:









(B) Pentru fiecare alegere a poziiei iniiale pentru 1 s[ se determine cte matrici
de tipul considerat exist[.


              IOI. 5 (Rescrieri). Un s-termen este o secven[ de caractere 's','('
,')' construit[ recursiv conform regulilor:
s este un s-termen;
Dac[ , sunt s-termeni, atunci () este un s-termen.
Exemple: ((((ss)(ss))s)s)) sau ((((ss(sss(ss
parantezele drepte putnd fi omise, ele neaducnd informaii noi.
Lungimea unei s-termen este num[rul de caractere 's' din el.
              1. Se citete de la intrare num[rul natural n<10. Se cere s[ se scrie o
procedur[ gensterm care s[  creeze pentru fiecare k=1,2,..,n un fiier text care
s[ conin[ toi s-termenii de lungime k; n fiier s-termenii sunt separai prin
';', iar fiierul se ncheie cu '.'.
              Se introduce asupra s-termenilor urm[toarea operaie, numit[ reducere:
orice s-subtermen avnd forma (((sA)B)C) (unde A,B,C sunt s-subtermeni)
poate fi transformat n ((AC)(BC))
adic[:        (((sA)B)C)((AC)(BC)).
                         Pentru simplificare vom spune n continuare termen n loc de s-termen.
Pentru un termen dat exist[ mai multe moduri n care poate fi ales un subtermen
asupra c[ruia se poate efectua reducerea. Prin normalizarea unui termen se nelege
aplicarea succesiv[ a reducerii att timp ct este posibil.
Exemplu de ir de reduceri: ((((ss(sss(ss(((ss((sss(ss
((s(ss(((sss(ss((s(ss((s(ss(s(ss.
              2. Alegei o structur[ de date adecvat[ pentru reprezentarea i reducerea
termenilor. Scriei dou[ proceduri readterm i printterm care s[ treac[ de la un
termen la reprezentarea aleas[ i invers. Demonstrai corectitudinea lor;
              3. Scriei o procedur[ reduce care s[ efectueze reducerea unui termen
asupra unui subtermen specificat i demonstrai corectitudinea ei;
              4. Scriei o procedur[ normalize care, pentru un termen dat, efectueaz[
succesiv reduceri pn[ cnd nu mai este posibil sau pn[ cnd num[rul de reduceri
dep[ete 30;
              5. Incorporai cele de mai sus ntr-un program care:
a) Citete o valoare pentru n;
b) utilizeaz[ termenii de lungime n generai de genterm;
c) transform[ aceti termeni n repezentarea aleas[;
d) i normalizeaz[ (dac[ este posibil); 
e) afieaz[ rezultatul normaliz[rii;
f) afieaz[ num[rul de reduceri efectuate pn[ la normalizare sau not normalized
dac[ acest num[r este 0 sau dep[ete 30;
g) afieaz[ num[rul de termeni de lungime n i num[rul de termeni normalizai.


              Ediia a IV-a (Bonn - Germania), iulie 1992

              IOI. 6 (Insule n mare) Marea este reprezentat[ printr-o reea p[trat[
de ordin N (1N8). Fiecare insul[ este identificat[ pe reea prin caracterul '*'.
Problema const[ din a reconstrui o hart[ a insulelor plecnd de la o informaie
codificat[ asupra distribuiei pe orizontal[ i vertical[ a insulelor. Un exemplu de
hart[ i de informaie codificat[ este urm[torul:
*     *  *                                                   1 2
   *  *  *     *                         3 1
*     *     *                                               1 1 1
   *  *  *  *  *                         5
*  *     *     *                         2 1 1
         *                                                     1

1  1  4  2  2  1
1  2     3     2
1
                         Numerele din dreapta fiec[rei linii reprezint[ n ordine m[rimea grupurilor
de insule adiacente situate pe acea linie. De exemplu, cifrele '1 2' care ncheie
prima linie semnific[ faptul c[ pe aceast[ linie apare un grup format dintr-o insul[,
urmat la dreapta de un grup format din dou[ insule; grupurile de insule sunt sepa-
rate ntre ele prin cel puin un blanc. Similar, secvena '1 1 1' care apare sub
prima coloan[ arat[ c[ pe aceast[ coloan[ apar trei grupuri de insule, fiecare grup
fiind format dintr-o singur[ insul[.
Se cere s[ se scrie un program care repet[ urm[torii pai pn[ cnd un fiier de
intrare dat, coninnd mai multe blocuri de informaie, este citit n ntregime:
              1) Citete urm[torul bloc de informaie din fiierul de intrare ASCII (cu
structura din exemplele de mai jos) i-l afieaz[ pe ecran. Fiecare bloc de informa-
ie const[ din ordinul reelei p[trate, urmat de restriciile referitoare la linii i apoi
de restriciile referitoare la coloane. Fiecare restricie apare pe o singur[ linie a
fiierului ca o secven[ de numere separate prin blancuri i terminat[ cu 0;
              2) Reconstruii harta (sau h[rile dac[ exist[ mai mult de o soluie) afind
rezultatul pe ecran;
              3) Scriei harta (h[rile) la sfritul unui fiier de ieire ASCII. Fiecare
blanc se reprezint[ ca o succesiune de dou[ blancuri, iar fiecare insul[ trebuie
reprezentat[ de caracterul '*' urmat de un blanc. Diferitele h[ri corespunz[toare
aceluiai bloc de informaie trebuie separate printr-o linie goal[. Dac[ nu exist[
nici o hart[ corespunz[toare blocului de informaie, indicai acest lucru printr-o
linie coninnd mesajul 'no map'. Soluiile pentru diferitele blocuri de informaie
trebuie separate printr-o linie coninnd mesajul 'next problem'.
Exemple:
6-                                    ordinul reelei
1 2 0-                    nceputul restriciilor pentru linii
3 1 0
1 1 1 0
5 0
2 1 1 0
1 0
1 1 1 0-                  nceputul restriciilor pentru coloane
1 2 0
4 0
2 3 0
2 0
1 2 0

4                                     Soluie:   1  2  3  4
0                                                                                                            1
1 0                                                                                                    2        *
2 0                                                                                                    3     *  *
0                                                                                                            4
0
1 0
2 0
0

2                                     Soluie: no map
0
0
2 0
2 0

2                                     Sunt dou[ soluii diferite.
1 0
1 0
1 0
1 0


              IOI. 7 (Urcarea unui munte) Un club de alpiniti are P(1P20)
membri, numerotai de la 1 la P. Toi au aceeai vitez[ de deplasare i vitezele la
urcare i coborre coincid. Alpinistul i consum[ C(i) unit[i de resurs[ pe zi,
indiferent ct car[, i poate c[ra cel mult S(i) astfel de unit[i. Toate numerele
sunt ntregi, citite de la tastatur[. Fie N(1N100) num[rul de zile n care dorim
s[ se ajung[ n vrf. Muntele poate fi ns[ foarte nalt astfel nct un singur alpinist
nu poat[ s[ ajung[ n vrf i s[ se ntoarc[ la baz[ cu resursele pe care le poate
transporta. De aceea un grup de alpiniti va pleca din acelai loc i n acelai
moment, cu scopul ca cel puin unul s[ ajung[ n vrf i toi s[ aib[ resurse sufici-
ente pentru a se ntoarce la baz[. Un alpinist care coboar[ nainte de a ajunge n
vrf cedeaz[ celorlali resursele suplimentare fa[ de cele necesare rentoarcerii sale
la baz[. Alpinitii nu se odihnesc pe parcursul drumului. Problema const[ n a
produce, dac[ exist[, o planificare de urcare.
              S[ se scrie un program care s[ realizeze urm[toarele:
              1) Citete de la tastatur[ (conform abloanelor din exemple) num[rul N de
zile n care trebuie s[ se ajung[ n vrf, num[rul P de alpiniti i numerele C(i),
S(i),1iP. Intr[rile f[r[ sens trebuiesc refuzate;
              2) Stabilete o planificare de urcare; determin[ un grup de alpiniti
a(1),a(2), ..,a(k) care s[ participe la urcare i (pentru toi j,1jk)
num[rul M(j) de resurse cu care pleac[ alpinistul a(j). De remarcat c[ nu
pentru orice date de intrare exist[ o planificare de urcare;
              3) Afieaz[ pe ecran:
- num[rul k de alpiniti care particip[ la urcare;
- num[rul total de resurse necesare;
- numerele de ordine a(1),a(2),..,a(k) ale alpinitilor participani;
- pentru fiecare j=1,2,..,k num[rul iniial de resurse M(j) cu care pleac[ 
alpinistul a(j);
- ziua D(j) cnd alpinistul a(j) ncepe coborrea;
              4) O planificare de urcare se numete optim[ dac[:
- num[rul de alpiniti care particip[ este minim;
- dintre grupurile satisf[cnd condiia precedent[ este ales cel pentru care cantitatea
total[ de resurse consumat[ este minim[.
              Se cere se determine o planificare aproape optim[.
 Exemplu: Un dialog posibil cu programul este:
Zile pentru a ajunge n vrf: 4
Num[rul membrilor clubului: 5
Maximul de resurse pentru alpinistul 1: 7
Consumul zilnic al alpinistului 1: 1
Maximul de resurse pentru alpinistul 2: 8
Consumul zilnic al alpinistului 2: 2
Maximul de resurse pentru alpinistul 3: 12
Consumul zilnic al alpinistului 3: 2
Maximul de resurse pentru alpinistul 4: 15
Consumul zilnic al alpinistului 4: 3
Maximul de resurse pentru alpinistul 5: 7
Consumul zilnic al alpinistului 5: 1
2 alpinisti necesari; cantitatea totala de resurse este 10
Alpinistii 1,5 pleaca
Alpinistul 1 cara 7 si coboara dupa 8 zile
Alpinistul 5 cara 3 si coboara dupa 1 zi
Alte date (Y/N) Y
Zile pentru a ajunge n vrf: 2
Num[rul membrilor clubului: 1
Maximul de resurse pentru alpinistul 1: 3
Consumul zilnic al alpinistului 1: 1
Urcare imposibila
Alte date (Y/N) N
Good bye













                         Ediia a V-a (Mendoza - Argentina), iunie 1993

              IOI. 8. (Colier). Se consider[ un colier format din n(n100) m[rgele,
care pot avea numai culorile rou (o), alb (&) sau albastru (*) aranjate ntr-un mod
arbitrar. In continuare apar dou[ exemple pentru n=29 n care sunt precizate pozi-
iile primeia i celei de-a doua m[rgele:
              1 2                             1 2
          o * * o                         * o o *
        o         *                     *         *
      o             o                 *             o
    o                 o             &                 o
  *                     o         &                     &
*                         *      o                      
o
*                         *      *                      
*
*                         *      o                      
*
  o                     o         *                     o
    *                 o             o                 o
       *            o                 o             o
         o        o                     o         *
           o * o                           o o &

In fiierul de intrare culorile m[rgelelor sunt indicate prin b (albastru), r (rou) i
w (alb). Astfel, colierul din prima figur[ de mai sus va fi reprezentat prin irul
                                    brbrrrbbbrrrrrbrrbbrbbbbrrrrb.
              Colierul se rupe ntre dou[ m[rgele consecutive. Plecnd de la ambele
capete spre centru se consider[ num[rul maxim de m[rgele consecutive de aceeai
culoare; fie M suma lor. La num[rare, un caz particular l constituie m[rgelele albe,
care pot fi recolorate n rou sau albastru astfel nct M s[ fie maxim.
              Se cer valoarea maxim[ a lui M i numerele de ordine ale m[rgelelor conse-
cutive ntre care se face t[ietura. Se cere o singur[ soluie pentru locul de t[ietur[.
              Fiierul de intrare este de tip text i conine cte o configuraie (colier) pe
fiecare linie. Un  exemplu este urm[torul:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrrb
              Rezultatele vor fi scrise ntr-un fiier de soluii. Rezultatele pentru
configuraii diferite vor fi separate ntre ele printr-o linie alb[. Un exemplu de fiier
corect de ieire pentru fiierul de intrare de mai sus este urm[torul:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
8 between 9 and 10

bbwbrrrwbrbrrrrrb
10 between 16 and 17
                         IOI. 9 (Bussines). Se consider[ un num[r de cel mult 100 companii.
Fiecare din ele poate deine procente din aciunile oric[rei alte companii. Fiind date
dou[ companii A i B, spunem c[ A controleaz[ compania B dac[ cel puin una
din urm[toarele condiii este ndeplinit[:
a) A=B;
b) A deine mai mult de 50% din B;
c) A controleaz[ k1 companii C(1),..,C(k), fiecare C(i) deine x(i)% din
B i x(1)+x(2)+..+x(k)>50.
              Se dau triplete {i,j,p} cu semnificaia: i deine p% din j. Se cer toate
perechile (h,s) astfel nct h controleaz[ compania s.
              Se cere s[ se scrie un program care s[ realizeze urm[toarele:
              1) Citete dintr-un fiier de intrare lista tripletelor. Testele (seturile
consecutive de date) sunt separate ntre ele printr-o linie liber[. Valorile i,j,p
sunt numere naturale;
              2) Determin[ toate perechile (h,s) astfel nct h controleaz[ s;
              3) Scrie n fiierul text de ieire toate perechile (h,s) determinate la (2),
cu hcs. Perechile (h,s) trebuiesc scrise n ordinea cresc[toare a lui h. Soluiile
pentru seturi de date diferite vor fi separate printr-o linie goal[.
Exemplu: Pentru fiierul de intrare
2 3 25
1 4 36
4 5 63
2 1 48
3 4 30
4 2 52
5 3 30

1 2 30
2 3 52
3 4 51
4 5 70
5 4 20
4 3 20
fiierul de ieire trebuie s[ aib[ forma:
4 2
4 3
4 5

2 3
2 4
2 5
3 4
3 5
4 5

                         IOI. 10 (Suprafee). N dreptunghiuri de culori diferite se suprapun succesiv pe o foaie alb[
de hrtie, de dimensiuni a,b. Dreptunghiurile se aeaz[ paralel cu laturile hrtiei i cad n interiorul
ei. Ca rezultat, v[znd de sus, se obin diferite figuri de diferite culori. Dou[ regiuni de aceeai
culoare se consider[ ca f[cnd parte din aceeai figur[ dac[ au cel puin un punct comun. Valorile
a,b sunt numere naturale pare, mai mici sau egale cu 30. Se cere aria fiec[rei figuri.
              Sistemul de coordonate are originea n centrul hrtiei i axele paralele cu laturile hrtiei.
Fiecare set de date are forma:
- prima linie conine valorile a,b,N separate ntre ele prin cte un blanc;
- urm[toarele N linii conin fiecare: coordonatele ntregi ale punctului din stnga jos al dreptunghiului
respectiv, urmate de coordonatele ntregi ale punctului de pe hrtie unde va fi plasat colul din dreapta
sus al dreptunghiului, urmat de culoarea acestuia, care este din domeniul [1,64]. Culoarea alb[ are
num[rul 1.
              Ordinea liniilor n fiierul de intrare corespunde ordinii de aezare a dreptunghiurilor. Seturile
diferite de date sunt separate ntre ele printr-o linie goal[.
              Se cere s[ se scrie un program care:
              1) Citete succesiv seturile de date din fiierul de intrare;
              2) Calculeaz[ aria fiec[rei figuri colorate, inclusiv n alb;
              3) Scrie ntr-un fiier text de ieire culoarea i aria fec[rei figuri, ca n exemplul urm[tor, n
ordinea cresc[toare a culorilor. Soluiile pentru seturi diferite de date sunt separate ntre ele printr-o
linie goal[.
Exemplu: Pentru fiierul de intrare:
20 12 5
-7 -5 -3 -1 4
-5 -3 5 3 2
-4 -2 -2 2 4
2 -2 3 -1 12
3 1 7 5 1

30 30 2
0 0 5 14 2
-10 -7 0 13 15
fiierul de ieire trebuie s[ aib[ forma:
1 172
2 47
4 12
4 8
12 1

1 630
2 70
15 200


              IOI. 11 (Turism). Suntei ctig[torul unui concurs organizat de compania aerian[ a
Canadei. Premiul const[ ntr-o c[l[torie cu avionul prin aeroporturile Canadei, c[l[torie supus[ unor
restricii.
              Nu exist[ dou[ aeroporturi situate pe acelai meridian. Se pleac[ din aeroportul situat cel mai
n vest, mergnd numai spre est, pn[ se ajunge la aeroportul cel mai din est; apoi ne ntoarcem,
mergnd numai c[tre vest, pn[ la aeroportul de plecare. Fiecare aeroport este vizitat cel mult odat[,
cu excepia celui de plecare, care este ns[ num[rat o singur[ dat[, dei se trece prin el de dou[ ori.
              Problema este urm[toarea: dndu-se lista aeroporturilor i conexiunile directe ntre ele, s[ se
determine (dac[ exist[) un itinerariu de forma precizat[, cerndu-se n plus s[ fie vizitate ct mai
multe aeroporturi.
              Fiierul de intrare este format din mai mullte seturi de date, separate ntre ele printr-o linie
goal[. Fiecare set de date are forma:
- pe prima linie apar num[rul N al aeroporturilor i num[rul V al liniilor directe; N i V sunt numere
naturale, N100;
- pe urm[toarele N linii apare cte un nume de aeroport. In fiierul de intrare numerele aeroporturilor
apar ordonate de la vest la est, adic[ aeroportul i este la est de aeroportul j dac[ i numai dac[ i>j;
numele fiec[rui aeroport este un ir de cel mult 15 caractere, care pot fi doar cifre i/sau litere;
- pe fiecare din urm[toarele V linii apare o pereche de nume de aeroporturi, separate printr-un blanc.
Astfel perechea:
city1 city2
are semnificaia c[ exist[ linie direct[ n ambele direcii ntre city1 i city2.
              Rezultatele vor fi nscrise n fiierul de ieire astfel:
- pe prima linie apare num[rul aeroporturilor prezente n fiierul de intrare;
- pe a doua linie apare num[rul M al aeroporturilor diferite cuprinse n itinerar;
- pe urm[toarele M+1 linii apar numele aeroporturilor, n ordinea n care au fost vizitate, cu precizarea
c[ primul aeroport (cel de plecare) este identic cu ultimul. Pentru orice set de date care nu admite
soluii vor fi scrise doar dou[ linii: pe prima apare num[rul aeroporturilor, iar pe a doua mesajul
NO SOLUTION;
- rezultatele pentru seturi diferite de date vor fi separate printr-o linie goal[.
Exemplu: pentru fiierul de intrare:
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

5 5
C1
C2
C3
C4
C5
C5 C4
C2 C3
C3 C1
C4 C1
C5 C2
un fiier corect de ieire este:
8
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

5
NO SOLUTION
 

              Ediia a VI-a (Stockholm - Suedia), iulie 1994

              IOI. 12 (Sume). S[ consider[m un triunghi format din n linii (1<n100), fiecare linie
coninnd numere ntregi din domeniul [1,99], ca n exemplul urm[tor:

                                                   7
                                                3     8
                                             8     1     0
                                          2     7     4     4
                                       4     5     2     6     5

              Problema const[ n scrierea unui program care s[ determine cea mai mare sum[ de numere
aflate pe un drum ntre num[rul de pe prima linie i un num[r de pe ultima linie. Fiecare num[r din
acest drum este situat sub precedentul, la stnga sau la dreapta acestuia.
Intrare: Fiierul de intrare are pe prima linie num[rul n, urmat de n linii coninnd numerele
triunghiului, separate prin cte un spaiu. Pentru exemplul anterior forma fiierului de intrare este:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Ieire: Ieirea este format[ dintr-un num[r care reprezint[ soluia problemei.

              IOI. 13 (Hart[). Figura de mai jos arat[ harta unui castel de form[ dreptunghiular[. Scriei
un program care determin[:
  i) Cte camere are castelul; se consider[ c[ exist[ totdeauna cel puin dou[ camere.
 ii) Suprafaa celei mai mari camere.
iii) Ce perete poate fi nl[turat pentru a obine o camer[ ct mai mare.
Intrare: un set de date de intrare este format din:
- pe prima linie, dou[ numere care reprezint[ m[rimea castelu-lui pe orizontal[ respectiv pe
vertical[; aceast[ m[rime este dat[ prin num[rul de module ce pot fi desf[urate pe fiecare latur[.
- pe urm[toarele linii, fiecare modul este caracterizat de un num[r n(0n15), format prin
nsumarea cifrelor 1 (dac[ modulul este delimitat n partea de vest printr-un perete), 2 (dac[ are
perete spre nord), 4 (perete la est), 8 (perete la sud). Pereii interiori sunt astfel definii de dou[ ori.
Ordinea de definire a modulelor este cea dat[ n exemplu.
Ieire: r[spunsul va fi dat pe trei linii:
  i) num[rul de camere;
 ii) aria celei mai mari camere (socotit[ n num[r de module);
iii) o reprezentare sugestiv[ a peretelui care trebuie eliminat (n caz c[ sunt mai multe soluii posibile,
se cere una din ele).
Exemplu: Pentru castelul definit de harta






fiierul de intrare va fi:
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
iar o ieire posibil[:
5
9
4 1 E
Aici, peretele care se poate elimina aparine modulului de pe a patra linie i prima coloan[, n partea
de est.


              IOI. 14 (Numere). Se consider[ tablourile p[tratice de dimensiune 5x5 formate cu cifre
ntre 0 i 9, n care suma cifrelor pe linie, coloan[ sau diagonal[ este aceeai. tiind c[:
- numerele de cinci cifre citite pe linie (de la stnga spre dreapta), coloan[ (citite de sus n jos) sau 
    de pe diagonale, sunt prime;
- pe prima linie sau coloan[ nu poate apare cifra 0 (deci nu este permis de exemplu 00003);
- cifra aflat[ n colul din stnga sus este cunoscut[;
- cifrele din interiorul p[tratului se pot repeta;
s[ se genereze toate tablourile astfel determinate.
Intrarea: este format[ din dou[ numere ntregi pozitive reprezentnd suma cifrelor pe o linie (coloan[
sau diagonal[) i respectiv cifra aflat[ n colul din stnga sus al p[tratului.
Ieirea: fiecare soluie va ocupa 5 linii, pe fiecare linie fiind cte un num[r prim de 5 cifre
reprezentnd linia respectiv[ din p[trat. Dou[ soluii distincte vor fi separate prin cte o linie cu
blancuri.
Exemplu: Pentru intrarea
11 1
exist[ trei soluii posibile date prin:
11351
14033
30323
53201
13313

11351
33203
30323
14033
33311

13313
13043
32303
50231
13331
                         IOI. 15 (Ceasuri). Nou[ ceasuri cu cte o singur[ limb[ sunt aezate ntr-un tablou 3x3.
Se definesc 9 modalit[i diferite de a nvrti cadranele acestor ceasuri, modalit[i date de figura
urm[toare:






Fiecare astfel de modalitate (codificat[ cu numere ntre 0 i 9) este
numit[ micare. Efectuarea unei mic[ri semnific[ rotirea
cadranelor situate n zona haurat[ cu 90o.
Intrare: Se citesc 9 numere care vor reprezenta poziiile de start ale
cadranelor ceasurilor din tablou. Marcarea va fi: 0 pentru limba
ceasului aezat[ la ora 12, 1 pentru ora 3, 2 pentru ora 6 i 3
pentru ora 9.
Ieirea: va fi cea mai scurt[ secven[ de mic[ri necesare pentru
a aduce limbile tuturor ceasurilor la ora 12.
Exemplu: pentru intrarea
3 3 0
2 2 2
2 1 2
ieirea este secvena
5849


             IOI. 16 (Autobuze). Un om sosete la staia de autobuz la ora 12.00 i st[ aici pn[ la
12.59. In staii sosesc autobuze de pe diverse trasee; omul nostru noteaz[ fiecare timp de sosire. Se
tie c[:
- autobuzele de pe fiecare traseu sosesc la intervale regulate de timp; sunt cel mult 17 trasee;
- n intervalul 12.00-12.59 fiecare traseu are cel puin dou[ opriri n staie;
- n acelai moment pot opri autobuze de pe mai multe trasee;
- pot fi trasee care au acelai timp de sosire i/sau aceeai perioad[ ntre dou[ opriri succesive. Dac[
exist[ dou[ rute cu acelai timp de plecare i aceeai perioad[, ele sunt distincte.
              Se cere s[ se determine cel mai mic num[r de trasee de autobuz care au oprire n staie.
Pentru fiecare astfel de traseu s[ se precizeze prima oprire din intervalul 12.00-12.59 precum i
intervalul dintre dou[ opriri.
Intrare: Fiierul de intrare conine num[rul n (2n300) care arat[ cte autobuze au oprit n staie;
el este urmat de toi timpii de sosire, scrii n ordine cresc[toare.
Ieire: Fiierul de ieire va avea cte o linie pentru fiecare traseu. Pe ea se afl[ momentul sosirii
primului autobuz i intervalul de timp (n minute). Ordinea de scriere a traseelor este arbitrar[. Dac[
sunt mai multe soluii, se cere numai una.      
Exemplu: La intrarea
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
ieirea este:
0 13
3 12
5 8


                         IOI. 17 (Sectoare de cerc). Se consider[ un cerc mp[rit n sectoare. Se dau la intrare
numerele k(k20),n(n6),m(m20); n reprezint[ num[rul de sectoare. In fiecare sector se
depune un num[r ntreg mai mare sau egal cu k. Aceste numere trebuiesc alese n aa fel nct s[ se
poat[ obine o secven[ ct mai mare de numere ntregi consecutive ncepnd cu m, construit[ astfel:
fiecare num[r este identic cu un num[r dintr-un sector sau este suma numerelor din dou[ sau mai
multe sectoare consecutive (luate o singur[ dat[). Ieirea trebuie s[ conin[:
- lungimea celei mai lungi secvene de numere care poate fi generat[ conform regulii de mai sus;
- toate combinaiile posibile de numere de pe cerc care pot produce aceast[ secven[ (cte una pe
linie). Fiecare astfel de combinaie este o list[ de numere ncepnd cu cel mai mic (care nu este
neap[rat unic).
Exemplu: pentru intrarea
1
2
5
ieirea va fi
21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4


              Ediia VII (Eindhoven - Olanda), iulie 1995


              IOI. 18 (???)  Se dau patru dreptunghiuri. S[ se determine cel mai mic dreptunghi (nou) n
care se pot introduce ele, f[r[ a le suprapune. Prin cel mai mic dreptunghi se nelege dreptunghiul
de arie minim[.
              Toate dreptunghiurile date trebuie s[ aib[ laturile paralele cu laturile dreptunghiului n care
se introduc. In Figur[  se arat[ cele ase moduri, singurele posibile, n care se pot grupa cele patru
dreptunghiuri date. Orice alt mod de aranjare se obine din acestea prin rotaie sau reflecie.
              Dac[ exist[ mai multe soluii posibile (dreptunghiuri de arie minim[), se cere listarea tuturor.
Intrare: 
Fiierul de intrare INPUT.TXT este format din 4 (patru) linii. Pe fiecare linie se d[ un dreptunghi prin
dou[ numere ntregi pozitive: lungimile laturilor (ordinea nu este important[). Fiecare latur[ a unui
dreptunghi este cel puin 1 i cel mult 50.
Ieire: 
Fiierul de ieire OUTPUT.TXT va conine cu o linie mai mult dect num[rul de soluii. Pe prima
linie va fi un singur num[r ntreg: aria minim[ a dreptunghiului g[sit (Subpunctul A). Fiecare din
liniile urm[toare va conine cte o soluie dat[ prin dou[ numere p i q, cu pq (Subpunctul B).
Aceste linii trebuie s[ fie toate diferite, sortate n ordine cresc[toare dup[ p.
Exemplu:
Pentru fiierul de intrare:
1 2
2 3
3 4
4 5
ieirea va fi:
40
4 10
5 8
                         IOI. 19 (???) Intr-un magazin, fiecare tip de produse are un pre. De exemplu, preul unei
flori este de 2 ICU (Informatics Currency Units) iar preul unui vas este de 5 ICU. Pentru a atrage
ct mai muli cump[r[tori, magazinul introduce anumite oferte speciale.
              O ofert[ special[ const[ din unul sau mai multe produse oferite la un pre mai mic. Exemple:
trei flori se dau pentru 5 ICU n loc de 6, sau dou[ vase mpreun[ cu o floare cost[ 10 ICU n loc
de 12.
              S[ se scrie un program care calculeaz[ preul pe care l d[ un cump[r[tor pentru o anumit[
solicitare. Costul trebuie s[ fie ct mai mic posibil, n funcie de ofertele speciale. Nu se poate ad[uga
nimic, chiar dac[ aceasta ar duce la sc[derea preului.
              Pentru preurile i ofertele din exemplul de mai sus, cel mai mic pre pl[tit pentru 3 flori i
2 vase este de 14 ICU: dou[ vase i o floare cost[ (redus) 10 ICU, iar 2 flori cost[ preul
(normal) de 4 ICU.
Intrare:
              Datele de intrare apar n doua fiiere: INPUT.TXT i OFFER.TXT. Primul fiier descrie
produsele (din "coul de cump[r[turi"). Al doilea fiier descrie ofertele speciale. Ambele fiiere conin
numai numere ntregi.
Prima linie din INPUT.TXT d[ num[rul b de produse diferite din coul de cump[r[turi (0b5).
Fiecare din cele b linii care urmeaz[ conine trei valori: c,k,p. Valoarea c este codul (unic) al unui
produs (1c999). Valoarea k indic[ cte buc[i din acest produs sunt n co (1k5). Valoarea
p este preul normal pentru fiecare bucat[ (1p999). De reinut c[ n co nu pot ncape mai mult
de 5*5=25 buc[i.
              Prima linie din OFFER.TXT conine num[rul s de oferte speciale (0s99). Fiecare din
urm[toarele s linii conine o ofert[ special[ dat[ prin structura sa i prin preul redus oferit. Primul
numar n de pe fiecare linie este num[rul de produse diferite care fac parte din ofert[ (1n5).
Urm[toarele n perechi de numere (c,k) indic[ situaia n care k buc[i (1k5) din produsul de
cod c(1c999) sunt n aceast[ ofert[. Ultimul num[r p de pe linie arat[ preul redus
(1p999); acest pre per ofert[ este mai mic dect suma preurilor normale.
Ieire: 
              Se scrie n fiierul OUTPUT.TXT o linie pe care se afl[ cel mai mic pre posibil care trebuie
pl[tit pentru produsele din fiierul de intrare.
Exemplu: Dac[:
INPUT.TXT
2
7 3 2
8 2 5
OFFER.TXT
2
1 7 3 5
2 7 1 8 2 10
atunci ieirea va fi
OUTPUT.TXT
14


               IOI 20 (???) Sunt doi utilizatori, fiecare din ei avnd cte un computer. Computerele sunt
identificate prin numele lor: CLIENT(1) i CLIENT(2). Cele dou[ computere deservesc una sau
mai multe imprimante, numite SERVER(1),SERVER(2), etc. Tip[rirea joburilor din ambele
computere se poate executa doar succesiv (nu n paralel !). Pentru a coordona comunicarea dintre cele
dou[ computere i o anumit[ imprimant[, se va folosi un obiect special numit semafor.

Semafor:
              Fiecare imprimant[ are un semafor. Fiecare semafor poate fi n una din st[rile S1 sau S2.
Cnd imprimanta poate primi de tip[rit un job, semaforul ei este n starea S1. Ct timp imprimanta
este ocupat[ cu tip[rirea unui job, semaforul este n starea S2.
              Un semafor poate face dou[ tipuri de treceri dintr-o stare n alta: "S1S2" sau 
"S2S1". Cnd un utilizator trimite computerului un job de tip[rit, acesta va trimite c[tre semafor
mesajul: "Are_you_open?". Dac[ starea semaforului este S1, atunci ea se va schimba n S2 i
semaforul va trimite mesajul "Open" calculatorului care l-a solicitat. Dac[ starea semaforului este S2,
atunci semaforul va r[spunde cu mesajul "Closed". Dup[ ce a terminat cu tip[rirea unui job,
imprimanta va trimite mesajul "Ready" c[tre semafor. La primirea mesajului "Ready", semaforul i
schimb[ starea n S1.
Obiect tip SEMAFOR:
              In Documentaia 1 se d[ specificarea obiectului tip SEMAFOR. Ea include identificatorii i
st[rile posibile ale unui obiect de tip SEMAFOR, "Priority List", "Communication Diagram", "State
Transition Diagram" i "Receive Procedures" pentru mesajele "Ready" i "Are_you_open?". 
              "Receive Procedures" descriu modul n care r[spunde un semafor la mesaje.
              "Priority List" este necesar[ deoarece mesajele care sunt primite n acelai timp de un semafor
trebuiesc prelucrate succesiv. Lista de priorit[i arat[ c[ orice mesaj al unui SERVER are o prioritate
mai mare dect orice mesaj de la un CLIENT i c[ serverele sunt listate n ordinea descresc[toare
a priorit[ilor: de exemplu, un mesaj de la SERVER(2) are o prioritate mai mare dect un mesaj de
la SERVER(3).
Obiect tip CLIENT:
              In Documentaia 2 se d[ specificarea obiectului tip CLIENT. Un obiect de tip CLIENT poate
fi n una din urm[toarele trei st[ri posibile: SA,SB sau SC. Un client este n starea SA dac[ nu a
trimis nici un job c[tre server i serverele nu sunt ocupate cu tip[rirea nici unui job al acestui client.
Un client care este n starea SB vrea s[ aib[ acces la un server. El poate avea acces la un server
numai via un semafor. Un client este n starea SC atunci cnd un server execut[ un job al acestui
client.
              Un client poate face trei tipuri de tranziii de st[ri: SASB,SBSC,SCSA.
Cnd un client este n starea SB, el poate primi de la semafor mesajul "Closed". In acest caz el
ateapt[ un timp dat de "Waiting_period" nainte de a trimite din nou semaforului mesajul
"Are_you_open?". Cnd semaforul trimite clientului mesajul "Open", clientul schimb[ starea n SC
i trimite jobul cu mesajul "S_Job" serverului legat de acest semafor. Acest server va executa jobul.
Dup[ ce a terminat, serverul va trimite dou[ mesaje n acelai timp: c[tre semafor - "Ready", i c[tre
client "C_Ready". La primirea mesajului, clientul i schimb[ starea din SC n SA. Se presupune c[
toate imprimantele lucreaz[ n condiii ideale; ele vor termina de tip[rit fiecare job trimis. De
exemplu, nu va fi niciodat[ ntalnit[ situaia "Out of paper".
Comunicarea:
              In Documentaia 3 se afl[ n "Communication Structure Diagram" toate tipurile de mesaje
care pot fi schimbate ntre tipurile de obiecte. In "Message List" se afl[ specificarea fiec[rui tip de
mesaj. Fiecare mesaj are un identificator, un expeditor, un destinatar i cteodat[ - un coninut.
              Cnd un expeditor trimite un mesaj cu identificatorul A la momentul t, la momentul t+1
destinatarul va prelucra mesajul executnd "Receive Procedure" A.
              Dac[ mai muli expeditori trimit mesaje la acelai destinatar la momentul t, atunci
destinatarul le va prelucra pe toate la momentul t+1 n ordinea n care expeditorii acestor mesaje apar
n lista "Priority List" a destinatarului.
SubProblema A:
              O reea local[ (LAN) conine la momentul 0 urm[toarele obiecte:

Obiect: CLIENT(1), Client.state=SA,
Waiting_Period=2, Number_of_Servers=1

Obiect: CLIENT(2), Client.state=SA,
Waiting_Period=1, Number_of_Servers=1

Obiect: SERVER(1)

Obiect: SEMAPHORE(1), Semaphore.State=S1

In acest LAN au fost trimise, printre altele, urm[toarele mesaje:
La momentul 1: CLIENT(1) trimite un mesaj cu identificatorul "Are_you_open?"
La momentul 2: CLIENT(2) trimite un mesaj cu identificatorul "Are_you_open?"
La momentul 4: SERVER(1) trimite un mesaj cu identificatorul "Ready"
La momentul 5: CLIENT(1) trimite un mesaj cu identificatorul "Are_you_open?"

              Documentaia 4 arat[ pentru SEMAPHORE(1),CLIENT(1) i CLIENT(2) ntr-o tabel[
pn[ la momentul 6, ce mesaje au primit aceste obiecte, ce masaje au trimis i n ce stare sunt sau
n ce stare se schimb[.
Intrebarea A.1:
Ce se va ntmpla dac[ - n plus - la momentul 4 CLIENT(1) primete un mesaj "C_Job" ?
Scriei r[spunsul pe un singur rnd n Documentaia 5.
Intrebarea A.2:
Ce se va ntampla dac[ la momentul 4 n loc de CLIENT(1),CLIENT(2) primete un mesaj
"C_Job" ?
Scriei r[spunsul n Documentaia 5.
Intrebarea A.3:
Completai tabela de timp din Documentaia 4 pn[ la momentul 13, dac[ apar urm[toarele situaii:
La momentul 8: SERVER(1) trimite un mesaj cu identificatorul "Ready";
La momentul 10: CLIENT(1) primete un mesaj cu identificatorul "C_Job";
La momentul 12: SERVER(1) trimite un mesaj cu identificatorul "Ready".
SubProblema B:
Reeaua LAN se extinde. Ea include acum dou[ perechi semafor-server:
                                   (SEMAPHOR(1), SEMAPHOR(2), SERVER(1), SERVER(2)).
Pentru fiecare CLIENT, Number_of_Servers este 2.
Pentru a folosi ambele imprimante este necesar[ modificarea definiiei obiectului CLIENT din
Documentaia 2.
In Documentaia 6 se afl[ schimbate "Receive_Procedures": C_Job i Wait.
Tot aici se afl[ o descriere a situaiei la momentul 0.
              In momentele care urmeaz[ sunt primite mesajele:
La momentul 0: CLIENT(1) primete de la un utilizator mesajul "C_Job".
La momentul 0: CLIENT(2) primete de la un utilizator mesajul "C_Job".
La momentul 4: SEMAPHOR(1) primete un mesaj "Ready".
              Ce se intampl[ n acest LAN extins (dac[ se folosete definiia modificat[ a obiectului tip
CLIENT) ?
Marcai r[spunsul corect n Documentaia 6.
SubProblema C:
              Definiia modificat[ a obiectului tip CLIENT din Subpunctul B nu a fost eficient[ pentru
acest LAN extins.

C.1.:
              Schimbai definiia obiectului tip CLIENT (vezi Documentaia 2) n aa fel nct, acest LAN
s[ poat[ funciona cu mai mult de o pereche semafor-server astfel:
-               Un obiect CLIENT(i) poate folosi orice server din LAN, dar CLIENT(i) poate avea la
un moment dat doar un job n curs de tip[rire de c[tre servere. Fiecare job al unui client este tip[rit
doar odat[.
-               Un obiect CLIENT(i) trimite un mesaj "Are_you_open?" succesiv la mai multe semafoare
pn[ cnd un anumit num[r (majoritar) de mesaje "Closed" este atins sau pn[ cnd obiectul
CLIENT(i) primete un mesaj "Open".
              Cnd obiectul CLIENT(i) atinge num[rul majoritar fixat de mesaje "Closed", el ateapt[
o anumit[ perioad[ "Waiting_Period" nainte de a ncepe s[ trimit[ din nou mesajele
"Are_you_open?".
Scriei soluia n Documentaia 7.
C.2.:
              Schimbai obiectul tip CLIENT n aa fel nct CLIENT(i) s[ poat[ avea acum posibilitatea
de a tipri mai multe joburi folosind simultan mai multe servere. Toui, num[rul de joburi tip[rite de
fiecare CLIENT(i) va fi limitat la CLIENT(i).Job_Maximum.
Scriei soluia n Documentaia 8.

Documentaia 1:
Tip obiect; SEMAFOR
              Identificatori posibili: (SEMAFOR(1),SEMAFOR(2),SEMAFOR(3),..)
              Stare: {S1,S2}; starea iniial[ este S1.
              Lista de priorit[i: SERVER(1),SERVER(2),..,CLIENT(1),CLIENT(2),..

Diagrama de comunicare:
(1) Are-you-open?(CLIENT(i),SEMAPHORE(j))
(2) Open(SEMAPHORE(i),CLIENT(j))
(3) Closed(SEMAPHORE(i),CLIENT(j))
(4) Ready(SERVER(i),SEMAPHORE(j))
(5)----------------------------------------------------------------------------------------------------------------
|                                                                                                        Diagrama de tranziie a st[rilor|
|                                                                                                               |
|                                                                                                                                                                                                                S1    S2|
|                                                                                                               |
-------------------------------------------------------------------------------------------------------------------
S[geile de lag[tur[ n diagrama de comunicare:
(1)(5)                 (5)(2)
(4)(5)                  (5)(3)

Procedurile de primire:
procedure Are-you-open?(Client,Semaphore)
begin
   if State=S1 then                      State S2
                                                                       Send(*Open(Semaphore,Client)*)
                else
                   if State=S2 then Send(*Closed(Semaphore,Client)*)
end
procedure Ready(Server,Semaphore)
begin StateS1 end

Documentaia 2:
Tip Obiect: CLIENT
              Identificatori posibili: c(CLIENT(1),CLIENT(2),CLIENT(3),...)
              Stare: {SA,SB,SC}; stare iniial[: SA
              Lista de priorit[i: CLIENT,SERVER(1),SERVER(2),..,SEMAPHOR(1),
                                       SEMAPHOR(2),..,USER(1),USER(2),..
              Num[r[tor: {t|tN}; valoarea iniial[ este 0.
              Waiting-Period: {t|tN, t>0};
              Semaphore-Index: {i|i=1,2,..,Number-of-Servers}
              Number-of-Servers: {i|iN, i>0}

Diagrama de comunicaie:
(1) C-Job(USER(i),CLIENT(j),DOCUMENT(k))
(2) S-Job(CLIENT(i),SERVER(j),DOCUMENT(k)) 
(3) Try-later(CLIENT(i),USER(j),EXPLANATION)
(4) Are-you-open?(CLIENT(i),SEMAPHOR(j))
(5) WAIT(CLIENT(i),CLIENT(i))
(6) C-Ready(SERVER(i),CLIENT(j))
(7) Open(SEMAPHORE(i),CLIENT(j))
(8) Closed(SEMAPHORE(i),CLIENT(j))
(9)----------------------------------------------------------------------------------------------------------------
                                           Diagrama de tranziie a st[rilor

                                                                                                                                                                                                                                                                                            SA
                                                                                                                                                                                                                                                                                               SC      SB

-------------------------------------------------------------------------------------------------------------------
S[geile de leg[tur[ n diagrama de comunicare:
(1)(9)                                          (9)(2)(6)(9)      (9)(3)
(9)(5)(9)                       (9)(4)            (7)(9)           (8)(9)

Procedurile de primire:
procedure C-Job(User,Client,Document)
begin
   if State=SA
      then StateSB
           Send("Are-you-open?(Client,SEMAPHORE(Semaphore-Index))")
      else if State=SB
              then Send("Try-later(Client,User,Client-is-busy)")
end
procedure Open(Semaphore,Client)
begin
   if State=SB
      then State  SC
           Send("S-Job(Client,Server,Document)')
end
procedure Closed(Se,aphore, Client)
begin
   Count-down  Waiting-period
   Send("Wait(Client,Client)")
end
procedure Wait(Client,Client)
begin
   Count-down  Count-down - 1
   if Count-down > 0
      then Send("Wait(Client,Client)")
      else Send("Are-you-open?(Client,SEMAPHORE(Semaphore-Index))")
end
procedure C-Ready(Server,Client)
begin
   State  SA
end

Documentaia 3:

Diagrama de structur[ a comunicaiei:
USER  (C-Job)  CLIENT  (Try-Later)  USER
CLIENT  (Wait)  CLIENT
CLIENT  (Are-you-open?)  SEMAPHORE  (Open, Close)  CLIENT
CLIENT  (S-Job)  SERVER  (C-Ready)  CLIENT
SERVER  (Ready)  SEMAPHORE

Lista de mesaje: (i,j,kN):
Identificator             Expeditor                Receptor                Coninut
Are-you-opern?                 CLIENT(i)                          SEMAPHORE(j)-      
C-Job                                              USER(i)CLIENT(j)                         DOCUMENT(k)
C-Ready                                          SERVER(i)CLIENT(i)-
Closed                                            SEMAPHORE(i)CLIENT(j)-
Open                                                           SEMAPHORE(i)CLIENT(j)-
Ready                                              SERVER(i)SEMAPHORE(j)-             
S-Job                                              CLIENT(i)SERVER(j)                     DOCUMENT(k)
Try-Later                                      CLIENT(i)  USER(j)                             EXPLANATION
Wait                                                           CLIENT(i)CLIENT(i)-

Documentaia 4:
Raspuns Subpunctul A.3.
              Semafor(1):
Timp          Mesaje primite   Stare/Tranziie   Mesaje trimise
0                                                                                                        S1
1                                                                                                            S1
2              Are-you-open?             S1S2                                   Open
3              Are-you-open?             S2                                              Closed
4                                                                                                            S2
               Ready                                 S2S1
5
               Are-you-open?             S1S2                                   Open
6              Are-you-open?             S2                                              Closed

7

8

9

10

11

12
13
                         Client(1):
Timp          Mesaje primite   Stare/tranziie              Num[r[tor     Mesaje trimise
0                                                                                                        SA0
1              C-Job                                 SASB           0                     Are-you-open?
2                                                                                                            SB0
3              Open                                        SBSC    0                       S-Job
4                                                                                                            SC0
5              C-Ready                             SCSA               0
               C-Job                                 SASB           0                     Are-you-open?
6

7

8

9

10

11

12

13

               Client(2):
Timp          Mesaje primite   Stare/tranziie              Num[r[tor     Mesaje trimise
0                                                                                                        SA0
1                                                                                                            SA0
2              C-Job                                 SASB           0                     Are-you-open?
3                                                                                                            SB0
4              Closed                               SB                 01             Wait
5              Wait                                        SB      10                     Are-you-open?

6

7

8

9

10

11

12

13

Documentaia 5:
Intrebarea A.1.
              Ce s-ar ntampla dac[ CLIENT(1) primete un mesaj "C-Job" la timpul 4 ?
.........................................................
Intrebarea A.2.
              Ce s-ar ntampla dac[ CLIENT(2) primete un mesaj "C-Job" la timpul 4 ?
Documentaia 6:
Problema B:
Procedurile C-Job si Wait modificate:
procedure C-Job(User,Client,Document)
begin
   if State=SA
      then State  SB
           for Semaphore-Index  1 step 1 until Number-of-servers
               Send("Are-you-open?(Client,SEMAPHORE(Semaphore-Index))")
      else if State=SB
              then Send("Try-later(Client,User,Client-is-busy)")
              else if State=SC
               then Send("Try-later(Client,User,All-Servers-are-busy)")
end
procedure Wait(Client,Client)
begin
   if State=Sb
     then Count-down  Countdown - 1
   if Count-down > 0
      then Send("Wait(Client,Client)")
      else if Count-down < 0
        then Count-down  0
        else for Semaphore-Index  1 step 1 until Number-of-Servers
                                       Send("Are-you-open?(Client,SEMAPHORE(Semaphore-Index))")
end

              La timpul 0 situaia n LAN este urm[toarea:
Obiect:       Client(1), Stare=SA, Waiting-Period=2, Number-of-Servers=2
               Client(2), Stare=SA, Waiting-Period=1, Number-of-Servers=2
Obiect:       SEMAPHORE(1), Stare=S1
               SEMAPHORE(2), Stare=S1
La urm[toarele momente se primesc mesajele:
Timpul 0: CLIENT(1) primete de la un utilizator un mesaj "C-Job";
Timpul 0: CLIENT(2) primete de la un utilizator un mesaj "C-Job";
Timpul 4: SEMAPHORE(1) primeste un mesaj "Ready".
              Ce se ntampl[ n LAN-ul extins relativ la obiectele CLIENT ? Marcai r[spunsul corect:

(a)           Jobul lui CLIENT(1) va fi tip[rit pe SERVER(1) i SERVER(2)
              Jobul lui CLIENT(2) nu este tip[rit

(b)           Jobul lui CLIENT(1) va fi tip[rit numai pe SERVER(1)
              Jobul lui CLIENT(2) va fi tip[rit numai pe SERVER(2)

(c)            Jobul lui CLIENT(1) va fi tip[rit numai pe SERVER(1)
              Jobul lui CLIENT(2) va fi tip[rit numai pe SERVER(1)

(d)            Jobul lui CLIENT(1) va fi tip[rit numai pe SERVER(2)
              Jobul lui CLIENT(2) va fi tip[rit numai pe SERVER(2)

(e)            Jobul lui CLIENT(1) nu este tip[rit
              Jobul lui CLIENT(2) va fi tip[rit pe SERVER(1) i SERVER(2)


Documentaia 7:
Subpunctul C.1.
..........................................

Documentaia 8:
Subpunctul C.2.
...........................................


              IOI 21 (???) Jocurile cu litere sunt populare. O variant[ const[ n asocierea de valori
numerice literelor; ulterior se alege o colecie de litere din care se pot forma unul sau mai multe
cuvinte pentru care valoarea numeric[ asociat[ este maxim posibil[.
Se dau valorile din Figur[, o list[ (dicionar) de cuvinte englezesti distincte i o colecie de litere. Se
cere s[ se determine cel mai mare scor posibil care poate fi obinut prin formarea cu litere din colecie
a unui cuvnt sau a unei perechi de dou[ cuvinte din dicionar. In cazul a dou[ cuvinte, acestea pot
s nu fie distincte.
Intrare:
              Fiierul de intrare INPUT.TXT conine o linie cu un ir de litere mici (de la 'a' la 'z'):
acestea formeaz[ colecia de litere. irul const[ din cel puin 3 i cel mult 7 litere alese n ordine
arbitrar[.
              Fiierul de intrare WORDS.TXT (dicionar) const[ din maxim 40.000 cuvinte, cte unul pe
o linie. El se termin[ cu un punct ('.'). Fiecare din celelalte linii conine un ir de minim 3 i maxim
7 litere mici. Cuvintele din fiier sunt distincte i ordonate alfabetic.
Ieire:
              Pe prima linie a fiierului de ieire OUTPUT.TXT trebuie scris cel mai mare scor posibil
(Subpunctul A); fiecare din celelalte linii conine cte o soluie: un cuvnt sau o pereche de cuvinte
din dicionarul WORDS.TXT care realizeaz[ acest scor (Subpunct B). Valoarea literelor folosite este
cea din Figur[. Cnd se poate forma o combinaie de dou[ cuvinte, ele vor fi scrise pe un singur
rnd, separate printr-un spaiu; ordinea nu are importan[; de exemplu, 'rag prom' i 'prom rag'
reprezint[ aceeai pereche i va fi scris[ o singur[ dat[.
Exemplu:
WORDS.TXT                                    INPUT.TXT
profile                                          prmgroa
program
prom
rag
ram
rom
OUTPUT.TXT
24
program
prom rag
Observaie: O liter[ nu poate apare de mai multe ori n fiierul de ieire dect n cel de intrare; pot
fi ns[ litere care s[ nu fie folosite.


              IOI. 22 (???)  Figura d[ exemplul unei curse pe str[zile unui ora. Se v[d anumite puncte,
notate de la 0 la N (aici N=9) i anumite arce care le leag[. Punctul 0 este punctul de start, iar N cel
final. Arcele reprezint[ str[zile cu sens unic pe care are loc cursa. Concurenii se deplaseaz[ pe
aceste str[zi, de la un punct la altul, doar n direcia indicat[ de s[gei. Ajuns ntr-un punct, un 
concurent poate alege s[ se deplaseze pe orice arc care pleac[ din punctul respectiv.
O curs[ bine definit[ are urm[toarele propriet[i:
1 - Orice punct al cursei poate fi atins plecnd din punctul de start;
2 - Finiul poate fi atins din orice punct al cursei;
3 - Din punctul final nu pleac[ nici un arc.
              Pentru a termina cursa, un participant nu este obligat s[ treac[ prin toate punctele. Unele
puncte ale cursei sunt totui de neocolit. In exemplu acestea sunt punctele 0,3,6 i 9. Fiind dat[ o
curs[ bine definit[, programul trebuie s[ determine mulimea punctelor de neocolit prin care trebuie
s[ treac[ toi participanii; excepie fac punctul de start i cel final (subpunctul A).
              S[ presupunem c[ aceast[ curs[ are loc n dou[ zile consecutive. De aceea ea trebuie
mp[rit[ ('spart[') n dou[ curse, cte una n fiecare zi. In prima zi punctul de start este 0 iar cel
final, unul din punctele de neocolit. In a doua zi punctul de start este acest punct de neocolit la care
s-a ajuns n ziua precedent[, iar punctul final este N. Fiind dat[ o curs[ bine definit[, programul
trebuie s[ determine mulimea punctelor de spargere (Subpunctul B).
              Un punct de spargere S pentru o curs[ bine definit[ C difer[ de punctul de start i cel final
ale lui C i are proprietatea c[ poate sparge cursa n dou[ curse bine definite care nu au arce comune
i n care singurul punct comun este S; de remarcat c[ buclele nu au influen[ asupra definiiei. In
exemplu, doar punctul 3 este punct de spargere.
Intrare:
              Fiierul INPUT.TXT descrie o curs[ bine format[ cu maxim 50 puncte i maxim 100 arce.
Fiierul conine N+1 linii: primele N linii dau punctele finale ale arcelor care pleac[ respectiv din
punctele de la 0 la N-1 (vezi exemplul). Fiecare linie se termin[ cu -2. Ultima linie conine num[rul
-1.
Ieire:
              Programul trebuie s[ scrie dou[ linii n fiierul OUTPUT.TXT. Prima linie va conine
num[rul punctelor de neocolit, urmat de m[rcile acestor puncte, ntr-o ordine arbitrar[ (Subpunctul
A). Pe a doua linie se afl[ num[rul punctelor de spargere, urmat de lista m[rcilor acestor puncte, n
orice ordine (Subpunctul B).
Exemplu:


              IOI. 23 (???) In Figur[, un cablu cu 3 fire leag[ partea A de partea B. Pe latura A, cele trei
fire sunt numerotate cu 1,2,3; pe latura B, firele 1 i 3 sunt legate la comutatorul 3 iar firul 2 este
legat la comutatorul 1.








              In general, cablul conine m fire (1m90) marcate de la 1 la m pe latura A, i m comutatoare
pe latura B, marcate de la 1 la m. Fiecare fir este legat exact la un comutator. In fiecare comutator pot
intra zero sau mai multe fire.
              Programul trebuie s[ determine modul n care se leag[ firele la comutatoare n aa fel nct
s[ ndeplineasc[ anumite cerine. Fiecare comutator poate nchide sau nu circuitul. Orice ap[sare pe
comutator i modific[ poziia: din nchis n deschis i invers. Iniial toate comutatoarele sunt pe poziia
deschis (nu circul[ curent). Un fir poate fi testat pe latura A cu proba P: 
P: Becul L se aprinde dac[ i numai dac[ firul este legat la un comutator care nchide circuitul.
              Programul va ncepe cu citirea unei linii care d[ num[rul m din intrarea standard. Pot fi date
trei tipuri de comenzi; fiecare va nsemna tip[rirea la ieirea standard a unei linii. O comand[ ncepe
cu una din literele T (test fir), C (apas[ pe comutator) i D (sfrit). Comanda T este urmat[ de
num[rul unui fir, C de num[rul unui comutator iar D, de o list[ n care al i-lea element este marca
comutatorului la care este legat firul i.
              Dup[ comenzile T i C, programul va citi o linie de la intrare. La comanda T r[spunsurile
posibile pot fi Y dac[ comutatorul la care este legat firul nchide circuitul (becul este aprins), i N n
caz contrar. Comanda C modific[ poziia comutatorului i: r[spunsul este Y dac[ noua poziie a
comutatorului este nchis, N dac[ este deschis. 
              Programul poate da comenzile T i C n orice ordine. Ultima comand[ este D urmat[ de lista
final[. Nu pot fi date mai mult de 900 comenzi n total.
Exemplu:
Iat[ cum arat[ o conversaie corespunz[toare exemplului din Figur[:
Standard Output                                         Standard Input
                                                                                                                3
C 3                                                                                                    Y
T 1                                                                                                    Y
T 2                                                                                                    N
T 3                                                                                                    Y
C 3                                                                                                    N
C 2                                                                                                    Y
T 2                                                                                                    N
D 3 1 3
Observaie: Pentru a asigura c[ n problem[ sunt folosite intrarea i ieirea standard, nu se va folosi
unitul CRT din Pascal.


                                            Alte probleme propuse de juriu

               Ediia I (Bulgaria)

               IOI. 24 (Amiciii). Se consider[ un grup de N persoane. Fiecare persoan[ are cel puin
[N/2] prieteni i cel mult K dumani n grup. Una dintre persoane are o carte pe care fiecare dorete
s[ o citeasc[ i apoi s[ o discute cu alte persoane. Se cere:
              1. S[ se determine un traseu prin care cartea s[ treac[ pe la toate persoanele din grup; fiecare
persoan[ o primete o singur[ dat[, o citete, o d[ unui prieten i cnd i se
returneaz[, o d[ celui de la care a primit-o.
              2. Pentru S i P date cu S*PK, s[ se mpart[ grupul n S subgrupuri n cadrul c[rora se
discut[ cartea, astfel nct fiecare persoan[ s[ nu aib[ mai mult de P dumani n subgrupul din care
face parte.


              IOI.25 (Icosaedru) Se consider[ un icosaedru (un poliedru regulat convex cu 20 fee) avnd
feele numerotate ntr-un mod dat de la 1 la 20. Prin rostogolire complet[ a icosaedrului nelegem
trecerea succesiv[ de la o fa[ la alta, adiacent[ ei, astfel nct s[ fie parcurse toate feele exact
odat[. Costul unei rostogoliri complete este de:
                                              c=1*f(1)+2*f(2)+..+20*f(20)
unde f(1),f(2),..,f(20) sunt n ordine feele care se parcurg. Se cere s[ se determine o
rostogolire complet[ de costminim, plecnd de la faa numerotat[ cu 1, n urm[toarele situaii:
                         1. Dou[ fee se numesc adiacente dac[ au o muchie comun[;
              2. Dou[ fee se numesc adiacente dac[ au cel puin un punct comun.


              IOI. 26 (Codificare). Se consider[ mesaje formate din litere mari i nc[ opt simboluri
suplimentare. Aceste mesaje sunt transmise printr-un canal de comunicaie printr-o codificare a
aracterelor componente ca o succesiune de K bii, astfel nct codificarea fiec[rui caracter s[ conin[
un num[r par de 1.
   1. Se cere s[ se produc[ o astfel de codificare n care K s[ fie minim;
   2. S[ se scrie un program capabil s[ codifice i s[ decodifice mesaje, conform codific[rii alese.


              IOI. 27 (Lifturi). Etajele unei cl[diri sunt numerotate secvenial cu numere ntregi 0,1,2,
..,N (N15). In cl[dire funcioneaz[ K(1K4) lifturi. Controlul liftului este centralizat i
accept[ dou[ tipuri de apel prin ap[sare pe butoane. Butoanele externe (unul pentru solicitarea de
urcare, cel[lalt pentru solicitarea de a cobor) se g[sesc pe fiecare etaj i sunt comune tuturor
lifturilor. Butoanele interne (pentru solicitarea de a ajunge la un anumit etaj) se afl[ n fiecare lift.
              Scriei un program care s[ modeleze controlul liftului pe baza urm[toarelor condiii:
1. Exist[ un singur lift n cl[dire (K=1) i el accept[ o singur[ solicitare la un moment. Orice alt[
cerere este luat[ n considerare dup[ ndeplinirea celei precedente.
2. Exist[ mai multe lifturi n cl[dire (K1). Fiecare din ele accept[ o cerere numai dac[ nu execut[
o alt[ solicitare. Aparatul de control al liftului poate nregistra mai multe solicit[ri n acelai timp.
Solicit[rile interioare sunt ndeplinite de liftul unde sunt nregistrate. Fiecare cerere extern[ este
repartizat[ de control unui lift liber.
3. Pentru acelai caz ca la (2), se introduce restricia ca lifturile cu num[r par s[ se opreasc[ numai
la etajele pare iar cele cu num[r impar, la etajele impare. Toate lifturile opresc la etajul 0 (parter).
4. S[ consider[m cazul (3) i s[ presupunem c[ pot fi mai multe cereri interne pentru fiecare lift,
nu numai una. Toate cererile interne sunt nregistrate i acceptate, indiferent dac[ un lift este liber sau
nu.
Condiii suplimentare:
              Se consider[ ca toate lifturile sunt sincronizate i c[ la intervale de timp egale cu unitatea
fiecare lift este la un anumit etaj. La momentul de timp urm[tor, un lift poate trece la etajul urm[tor
(sus sau jos) sau poate r[mne la acelai etaj. Solicit[rile (intr[ri n program) pot fi f[cute la orice
moment i sunt de urm[toarele tipuri:
a) externe: <num[rul etajului, direcia mic[rii (sus sau jos)>;
b) interne: <num[rul liftului, num[rul etajului>.
La fiecare moment pot fi nregistrate zero, una sau mai multe solicit[ri.
La fiecare moment programul va afia informaia referitoare la poziia fiec[rui lift.
Lifturile sunt suficient de mari i nu pot fi supranc[rcate.
Programul va controla lifturile dup[ o strategie ct mai "inteligent[" posibil.


              Ediia II (Bielorusia):


               IOI. 27 (Cititori) Doi cititori, A i B, doresc s[ citeasc[ N c[ri numerotate de la 1 la N.
Pentru fiecare I(1IN), cartea I este citit[ de A n A[I] ore, iar de B n B[I] ore. Citirea ncepe
att pentru A ct i pentru B de la timpul 0. La fiecare moment de timp, un cititor nu poate citi dect
o singur[ carte, iar o carte nu poate fi citit[ simultan de ambii cititori. Mai mult, citirea unei c[ri
poate fi ntrerupt[ dup[ un num[r ntreg de ore i reluat[ ulterior, ntre timp putndu-se citi din alt[
carte.
                         Este de asemenea dat un num[r K(2KN), avnd urm[toarea semnificaie: pentru orice
J(2JN), citirea c[rii J poate fi nceput[ doar dac[ ambii cititori au citit n ntregime cartea J-1.
              1. Se cere s[ se calculeze cel mai mic timp T n care att A ct i B citesc toate cele N c[ri;
              2. S[ se produc[ la ieire o schem[ de citire a c[rilor de c[tre cei doi cititori n timpul T
determinat mai sus.


              IOI.28 (Intersecii). Se dau la intrare num[rul natural N i segmentele n plan
[a(i),b(i)], 1iN. Se cere s[ se determine num[rul maxim de segmente intersectate de o
aceeai dreapt[.


              IOI.29 (Hauri).  Se citesc de la intrare numerele naturale N,K(KN40). Se consider[
o band[ de hrtie mp[rit[ n N c[sue adiacente. Juc[torii 1 i 2 aleg alternativ, ncepnd cu
juc[torul 1 o secven[ de K celule consecutive nehaurate i le haureaz[. Ctig[ juc[torul care
efecteaz[ ultima mutare.
              1. Se cere s[ se determine dac[ juc[torul 1 are strategie sigur[ de ctig;
              2. n caz afirmativ, s[ se programeze modul n care acioneaz[ juc[torul 1, mut[rile
juc[torului 2 fiind citite de la tastatur[.


              IOI. 30 (Generare cod). Se consider[ un limbaj de programare care admite numai
instruciuni de urm[toarele dou[ tipuri:
x:=y;
x:=y*z;
unde x,y,z sunt variabile ntregi, nu neap[rat distincte. Fiind date valorile naturale a,n(n<100)
se cere s[ se scrie n acest limbaj un program care s[ calculeze b=an cu un num[r minim de
nmuliri. Pot fi utilizate oricte variabile suplimentare. 
De exemplu pentru n=13, un astfel de program este urm[torul:


x1:=a;
x2:=x1*x1;
x3:=x2*x2;
x4:=x3*x1;
x5:=x3*x3;
x6:=x4*x5;
b:=x6;


               Ediia III (Grecia):


               IOI.31 (Ferm[). Un fermier dorete s[ p[zeasc[ plantaia sa de arbori rari. Pentru aceasta
se cere s[ se mprejmuiasc[ cu srm[ aceti arbori, astfel nct lungimea total[ a srmei s[ fie cea
mai mic[ posibil[; ia natere astfel un poligon. De asemenea fermierul dorete s[-i construiasc[ o
cas[ de form[ dreptunghiular[, avnd laturile paralele cu axele Ox,Oy, precizndu-se coordonatele
a dou[ vrfuri opuse. Scriei un program care:
- determin[ arborii care sunt vrfurile poligonului de perimetru minim cu condiiile de mai sus;
- calculeaz[ lungimea srmei necesare;
- indic[ poziia casei fa[ de poligonul de mai sus, preciznd dac[;
-               casa este exterioar[ poligonului;
-               casa este interioar[ poligonului;
-               casa mparte poligonul n dou[ regiuni cu arii nenule.


              IOI.32 (Un joc de c[ri). Se consider[ un pachet de 52 c[ri avnd valorile 
                                            1 (as),2,3,4,5,6,7,8,9,10,J,Q,K
n fiecare din cele patru culori (trefl[, caro, cup[, pic[).
              In prima faz[ trebuie create pe ecran trei rnduri de cte patru c[ri, prin extragerea pe rnd
a unei c[ri din pachet i plasarea ei pe mas[ (dac[ se extrage ns[ J,Q sau K, aceast[ carte este
plasat[ la sfritul pachetului de c[ri). In continuare se fac elimin[ri, ct timp este posibil; o
eliminare const[ n determinarea a dou[ c[ri de pe mas[ a c[ror sum[ este 10 sau 20, nl[turarea
lor din joc i nlocuirea lor cu alte dou[ c[ri din pachet.
              Se cere s[ se simuleze acest joc pe ecran.


              IOI.33 (Recunoaterea unei limbi str[ine). 1. Se citete la intrare un text ASCII
reprezentnd un text scris ntr-o limb[ necunoscut[. Se cere:
a) S[ se determine mulimea caracterelor care apar n text;
b) s[ se modifice textul nlocuind literele mici cu litere mari iar orice caracter diferit de liter[ cu
blanc; pentru fiecare  dintre caracterele mulimii {' ','A',..,'Z'} se va determina frecvena sa
de apariie relativ[ la textul respectiv.
              2. Se citesc de la intrare un num[r natural N i N texte n limbi diferite specificate. Se citete
apoi un text suplimentar, care trebuie comparat cu cele N etxte citite anterior cu scopul de a determina
n care dintre limbile date este cel mai probabil de a fi fost scris. Criteriul de comparare va fi ales de
c[tre programator i va fi specificat explicit.





               Ediia IV (Germania):

               IOI.34 (Robotul lui Hamilton). Se dau n plan n puncte cu coordonate ntregi
P1(X1,Y1),P2(X2,Y2)..,Pn(Xn,Yn). Un robot pleac[ din P1 i trebuie s[ treac[ prin toate aceste
puncte. El va trece exact odat[ prin fiecare punct i s[ revin[ n P1. Micarea robotului este supus[
unor restricii. El se poate deplasa doarde-alungul unor linii drepte. Din P1 el se poate deplasa n orice
direcie. Odat[ ajuns ntr-un punct Pi trebuie ca, nainte de a se deplasa ntr-un alt punct, s[ se
roteasc[ cu 90o fie la stnga fie la dreapta. pentru micarea robotului sunt disponibile urm[toarele
cinic instruciuni:
1) ORIENTATION Xk Yk: robotul se orienteaz[ spre poziia Pk(2kn); aceast[ instruciune poate
fi folosit[ doar ca prima instruciune din program;
2) MOVE-TO Xj Yj: dac[ robotul poate ajunge n Pj f[r[ s[-i schimbe orientarea, arunci el se
va deplasa n Pj;
3) TURN-LEFT: robotul i schimb[ orientarea cu 90o spre stnga;
4) TURN-RIGHT: robotul i schimb[ orientarea cu 90o spre dreapta;
5) STOP: oprete micarea robotului; este obligatoriu ultima instruciune a programului.
              S[ se scrie un program care realizeaz[ urm[toarele:
a) Citete de pe prima linie a unui fiier de intrare ASCII valoarea lui n (4n16) i apoi
coordonatele celor n puncte (cte un punct pe fiecare linie); afieaz[ aceste date pe ecran.
b) Determin[ dac[ exist[ un circuit care s[ treac[ prin toate poziiile (n modul definit mai sus).
c) Dac[ nu exist[ un astfel de circuit, programul pentru robot va conine nuai instruciunea STOP.
d) Afieaz[ pe ecran dac[ exist[ sau nu un astfel de circuit; n caz afirmativ, afieaz[ lungimea
circuitului determinat, cu aproximaie de dou[ cifre.
e) Scrie programul robotului ntr-un fiier de ieire ASCII, ca n exemplu.
Exemplu: pentru datele de intrare
4
2 -2
0 2
-1 -1
3 1
Cel mai scurt drum pentru robot are lungimea 12.65 i este dat de programul
ORIENTATION 3 1
MOVE-TO 3 1
TURN-LEFT
MOVE-TO 0 2
TURN-LEFT
MOVE-TO -1 -1
TURN-LEFT
MOVE-TO 2 -2
STOP


               IOI.35 (Paranteze). Se introduce de la tastatur[ un num[r natural N100. Se cere s[ se
calculeze num[rul irurilor de caractere de lungime N care conin doar paranteze rotunde deschise i
nchise, cu proprietatea c[ parantezele se potrivesc corect.
Exemplu: Pentru N=4 irurile corecte sunt:
()()
(())
deci la ieire trebuie produs num[rul 2. 




              IOI.36 (Cuvinte ncruciate). Consider[m un careu de cuvinte ncruciate. P[tr[elele
(punctele) negre sunt marcate cu asterisc, iar celelalte cu litere mari. O form[ uzual[ de reprezentare
const[ n furnizarea a dou[ liste de cuvinte, coninnd cuvintele pe orizontal[, respectiv pe vertical[.
Fiecare cuvnt din aceste liste este precedat de un num[r ataat p[tr[elului de nceput al s[u. Dorim
ca un num[r minim de p[tr[ele s[ aib[ asociate numere. Mai mult, numerele ataate p[tr[elelor
trebuie s[ fie consecutive, ncepnd cu 1; numero-tarea se face pe linii, iar n cadrul fiec[rei linii, de
la stnga la dreapta.
Intrarea: Datele se citesc dintr-un fiier text, al c[rui nume se introduce de la tastatur[ i are forma:
L  C
linia 1
.......
linia L
unde L este num[rul de linii iar C este num[rul de coloane (L20,C20).
Ieirea se face ntr-un fiier text n care apare lista cuvintelor de pe orizontal[ precedat[ de cuvntul
ORIZONTAL i apoi lista cuvintelor de pe vertical[ precedat[ de cuvntul VERTICAL.
Exemplu: Pentru fiierul de intrare 
4  4
AC*S
BAIE
AS*T
C*IE
fiierul de ieire trebuie s[ aib[ coninutul:
ORIZONTAL
1.AC
3.S
4.BAIE
6.AS
7.T
8.C
9.IE
VERTICAL
1.ABAC
2.CAS
5.I
9.I
3.SETE

              IOI. 37 (Maxim i minim). Un fiier text de intrare, al c[rui nume este citit prin program,
conine pe prima linie numerele naturale L i S (L,S20), iar pe a doua linie o secven[ de cifre
zecimale ce sunt n ordine cifrele num[rului natural N (N200, L*CN). Se cere s[ se afieze:
   - cifrele succesive ale celui mai mic num[r natural obinut din N prin S tergeri a cte L cifre aflate
pe poziii consecutive;
   - cifrele succesive ale celui mai mare num[r natural obinut din N prin S tergeri a cte L cifre
aflate pe poziii consecutive.


              IOI. 38 (Banda lui Mbius). Se consider[ un film fotografic n care pe fiecare clieu i
sunt nscrise o valoare ntreag[ Ai pe faa de deasupra i o valoare ntreag[ Bi pe faa de dedesubt
(1iN100). Valorile componentelor celor doi vectori sunt citite de pe liniile a doua i a treia ale
unui fiier text al c[rui nume se citete prin program (prima linie conine valoarea lui N). Filmul este
r[sucit o dat[ i capetele sale sunt unite, obinndu-se o band[ a lui Mbius n care toate numerele
nscrise se afl[ pe aceeai parte. Pe aceast[ band[ sunt permise urm[toarele operaii:
  - Ri: clieul i este rotit (valorile Ai,Bi i schimb[ locurile ntre ele);
  - Iij: clieele i,j se interschimb[ ntre ele, f[r[ rotirea lor.
                         Se cere ca printr-o succesiune de operaii permise, numerele aflate pe banda lui Mbius s[
apar[ n ordine nedescresc[toare (evident, ncepnd cu o anumit[ poziie). O succesiune rezultat de
operaii va fi nscris[ n fiierul text de ieire astfel: pentru fiecare operaie, pe o prim[ linie vor apare
litera i indicele (indicii) care identific[ operaia efectuat[, iar pe o a doua linie va apare succesiunea
celor 2N numere, ncepnd cu poziia pe care s-a aflat iniial Ai.
Exemplu: Pentru fiierul de intrare
4
15   5   2   8
 7  12  10  17
o ieire corect[ are forma:
I  1  3
2  5  15  8  10  12  7  17
R  3
2  5  7  8  10  12  15  17


             IOI. 39 (Vizibilitate). Se consider[ o linie frnt[ nchis[ P1P2..PNP1 care nu se
autointersecteaz[ (N100). Un observator este situat n punctul A. Fiecare din segmentele linie frnte
poate fi pentru observator:
   - invizibil (I);
   - vizibil parial (P);
   - vizibil total (T).
(cazul n care vizibilitatea se reduce la un punct este asimilat cu invizibil).
Intrarea este constituit[ de un fiier text al c[rui nume se citete prin program i are forma:
   - prima linie conine valoarea lui N;
   - urm[toarele N linii conin n ordine cte dou[ numere ntregi ce reprezint[ abscisele i ordonatele
punctelor consecutive ale liniei frnte, ncepnd cu P1;
   - ultima linie conine abscisa i ordonata observatorului.
Ieirea se va face ntr-un fiier text n care pentru fiecare segment PiPj al liniei frnte se va scrie pe
o linie tripletul de valori i,j,c unde c este una dintre literele I,P,T cu semnifi-caia de mai sus.


              Ediia a VI (Suedia)

               IOI. 40 (Rame de tablouri). Se consider[ N rame de tablouri (N20) avnd marginile de
dimensiune 1; fiec[rei rame i este asociat[ o liter[ mare, care este nscris[ pe toate p[tr[elele
componente ale ramei. Ramele se aeaz[ una peste alta, cu laturile paralele cu axele i cu vrfurile
n puncte de coordonate ntregi. Toate ramele sunt incluse ntr-o fereastr[ dreptunghiular[ avnd
colul din stnga-jos de coordonate (0,0). Privind de sus vedem doar fragmente de rame. Se cere
s[ se determine ordinea n care au fost plasate ramele vizibile.
Intrarea este dat[ de un fiier text INT.TXT. Pe prima linie apar n[limea H i l[imea L a ferestrei
(0L,H30). Urmeaz[ H linii coninnd fiecare cte L caractere i reprezentnd liniile vizibile;
fondul ferestrei este reprezentat prin puncte.
Ieirea se face pe ecran i const[ dintr-un ir de litere mari reprezentnd n ordine ramele care au fost
aezate n fereastr[.
Exemplu: Pentru fiierul de intrare:
9  8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
ieirea va avea forma
CBADE


             IOI. 41 (Rute aeriene). O companie de transporturi aeriene situat[ n oraul 1 deine un
singur avion, care trebuie s[ asigure transporturi ntre oricare dintre oraele identificate cu 1,2,..,N
(N10). Distanele ntre aceste orae sunt date printr-o matrice citit[ de la intrare.   
              In fiecare diminea[, compania primete lista zborurilor directe dintre perechi de orae, zboruri
obligatorii pentru satisfacerea tuturor cererilor de transport. Se cere o rut[ a avionului care:
   - ncepe din oraul 1 i se termin[ tot n oraul 1;
   - trebuie s[ cuprind[ toate zborurile directe specificate;
   - trebuie s[ aib[ lungime minim[.
Intrarea const[ dintr-un fiier text al c[rui nume se citete de la tastatur[ i n care:
- prima linie conine num[rul N de orae;
- urm[toarele N linii sunt liniile matricii distanelor directe dintre orae;
- urm[toarea linie conine num[rul Z de zboruri directe obligatorii ce trebuie efectuate n ziua
respectiv[;
- urm[toarele Z linii conin fiecare cte o pereche ordonat[ de orae identificnd aceste zboruri directe
obligatorii.
Ieirea se face pe ecran i const[ din dou[ linii: pe prima linie apare lungimea rutei optime, iar pe
a doua linie apar n ordine numerele ce identific[ oraele situate pe o astfel de rut[, sepa-rate ntre
ele printr-un blanc.
Exemplu: Pentru fiierul de intrare
7
 0  56  43  71  35  41  36
56   0  54  58  36  79  31
43  54   0  30  20  31  58
71  58  30   0  38  59  75
35  36  20  38   0  44  70
41  79  31  59  44   0  72
36  31  58  75  70  72   0
5
6  3
1  5
2  4
7  2
7  1
o ieire corect[ este:
368
1  5  6  3  7  2  4  7  1


             IOI. 42 (Obstacole). Se consider[ o reea p[trat[ n care un mobil trebuie s[ se deplaseze
pe un traseu de lungime minim[ din punctul (0,0) n punctul (100,100).
Dificultatea const[ n existena a N obstacole (N30) care nu pot fi intersectate (nici un punct interior
al lor nu se poate afla pe traseul soluiei). Se tie c[:
   - obstacolele sunt p[trate cu latura de lungime 5; laturile sunt paralele cu axele de coordonate;
   - colurile obstacolelor au coordonate ntregi;
   - nu exist[ dou[ obstacole avnd vreun punct comun.
Intrarea este constituit[ de un fiier text al c[rui nume este citit prin program i n care:
- prima linie conine num[rul N de obstacole;
- fiecare dintre urm[toarele N linii conine abscisa i ordonata colului stnga-jos al unui obstacol.
Ieirea se face pe ecran. Pe cte o linie apar succesiv coordona-tele punctelor traseului-soluie n care
mobilul i schimb[ direcia.
Exemplu: Pentru fiierul de intrare
5
 5   5
 5  15
15  10
15  20
90  90
o ieire corect[ este:
0  0
5  10
20  20
95  90
100  100


             IOI. 43 (Imp[turirea h[rilor). O hart[ dreptunghiula-r[ avnd L linii i C coloane pate
fi mp[turit[ n diverse moduri (L8,C8,L*C16). P[tratele h[rii sunt etichetate n ordinea
liniilor cu literele A,B,C,.. De la tastatur[ se citesc, de pe cte o linie, valorile L i C i un cuvnt
format din primele L*C litere mari, ntr-o ordine oarecare. Problema const[ n a mp[turi harta astfel
nct n final s[ se obin[ cuvntul citit, dac[ vom considera etichetele p[tr[elelor h[rii pliate n
ordine de sus n jos. O pliere are una din formele:
   - SnD: se pliaz[ harta de-a lungul celei de a n-a verticale de pliere posibile, cu partea din stnga
peste cea din dreapta;
   - DnS: se pliaz[ harta de-a lungul celei de a n-a verticale de pliere posibile, cu partea din dreapta
peste cea din stnga;
   - JnS: se pliaz[ harta de-a lungul celei de a n-a orizontale de pliere posibile, cu partea de jos peste
cea de sus;
   - SnJ: se pliaz[ harta de-a lungul celei de a n-a orizontale de pliere posibile, cu partea de sus peste
cea de jos.
              Dup[ fiecare pliere, noile orizontale i verticale de pliere posibile sunt renumerotate ncepnd
cu 1.
              Soluia va fi furnizat[ pe ecran, cu tripletele separate ntre ele printr-un blanc.
Exemplu: Pentru datele de intrare
3
4
HDLFEABIJKCG
o ieire corect[ are forma:
S1D  S1J  J1S  S1D  D1S

             Ediia a VII (Olanda)

               IOI. 44 (faulty links). Problema se refer[ la comunicarea mesajelor de la un produc[tor
la un consumator (vezi Figura 1). Un mesaj este un bit din mulimea {0,1} sau un indicator de
eroare E.
              Produc[torul P formeaz[ o secven[ de mesaje pe canalul s[u de ieire (vezi Figura 2).
Consumatorul C consum[ o secven[ de mesaje din canalul s[u de intrare y (vezi Figura 3). S[
not[m cu pi (pi{0,1},i0) secvena realizat[ i cu ci (i0) secvena consumat[.
Ideal ar fi s[ putem garanta c[ C consum[ exact secvena produs[ de P, adic[ pi=ci zi0.
In particular, orice bit trimis de P va ajunge la C exact odat[ dup[ un num[r finit de pai. O
soluie ar fi obinut[ conectnd ieirea canalului lui P direct la intrarea canalului lui C (vezi Figura
4). In aceast[ problem[ din p[cate, P i C sunt la distan[ mare i vor fi legai prin intermediari de
comunicare perturbatori (faulty communication links).
              Un intermediar de comunicare perturbator L, numit pe scurt o leg[tur[, are un canal de
intrare x i un canal de ieire y (vezi Figura 5). El copiaz[ pe y fiecare mesaj primit prin x; uneori
poate ns[ strica mesajele. Stric[ciunea este ns[ detectabil[: orice mesaj stricat conine un caracter
distinct de eroare E{0,1}, care nu apare n mesajele corecte.
               In aceast[ problem[ nu vom considera leg[turi care stric[ toate mesajele ncepnd
cu un anumit moment. Deci o leg[tur[ poate strica numai un num[r finit de mesaje
consecutive (Figura 5). Sau altfel spus: dac[ un mesaj este repetat suficient de des, el va fi
eventual transmis corect.
               S[ conect[m canalul de ieire al lui P la canalul de intrare al unei leg[turi L i canalul
de ieire al lui L la canalul de intrare al lui C (vezi Figura 6).
Aceast[ configuraie nu lucreaz[ sigur, deoarecemesajele pot fi stricate ideci pierdute; de exemplu,
putem avea p0=0 i c0=E.

                                                                                                                                                                  sf   L(sf,fr)   fr
P(x)   x      S(x,sf,bs)                                                                                                                                                           R(fr,bs,y)   y   C(y)
                                                                                                                                                                  bs   L(rb,bs)   rb

Produc[tor    Expeditor                           Leg[tur[ de corecie              Receptor         Consumator

                                                       Figura 1
                           Conectarea de la P la C via dou[ L-leg[turi i protocoale S i R

P=proc(x!Msg).                                                                                                                         C=proc(y!Msg).
begin i:var Nat & m:var Msg                               begin i:var Nat & m:var Msg
| i:=0                                                                                                                                                                               | i:=0
; forever                                                                                                                                                                ; forever
  do m:=pi; x!m                                                                                                                           do y?m; ci:=m
  ; i:=i+1                                                                                                                                               ; i:=i+1
  od                                                                                                                                                                                                      od
end                                                                                                                                                                                                          end

 Figura 2: Program pentru produc[torul P                 Figura 3: Program pentru consmatorul C

               P(z)    z    C(z)                                            P(x)   x   L(x,y)   y   C(y)

                                     Figura 4                                     Figura 6
     Conectarea direct[ de la P la C                                  Conectarea de la P la C via L

                                       L=proc(x?Msg & y!Msg).
                                       begin m:var Msg & n:var Nat
                                       | forever
                                         do n:Nat
                                          ; for n do x?m; y!E od
                                          ; x?m; y!m
                                         od
                                       end

                                                                    Figura 5
                                     Program pentru o leg[tur[ cu erori L

Protocolul de retransmisie:
              Putem preveni pierderea mesajelor retransmind mesajele stricate. Pentru aceasta este necesar[
o leg[tur[ n sens invers, numit[ leg[tur[ de corecie; cealalt[ leg[tur[ este numit[ leg[tur[ de
transmisie. Protocolul de retransmisie este implementat la expeditorul S pe partea lui P i la
destinatarulR pe partea lui C. S i R sunt legai unul de altul att prin leg[turi de transmisie ct i
de corecie (vezi Figura 1).
              Expeditorul S (vezi Figura 7) citete un mesaj din P i-l trimite lui R via leg[tura de
transmisie. Apoi S ateapt[ de la R un bit de confirmare via leg[tura de corecie. Bitul c1 indic[ o
recepie corect[ iar bitul 0 - o recepie greit[. S va repeta transmisia mesajului pn[ va primi bitul
1, dup[ care se proceseaz[ urm[torul mesaj din P.
              Destinatarul R (vezi Figura 8) primete un mesaj prin leg[tura de transmisie; dac[ acesta este
greit, R cere retransmisia expediind un bit 0 via leg[tura de corecie. Dac[ se primete un mesaj
nestricat, R l scoate c[tre C i - n acelai timp - trimite un bit 1 lui S prin linia de corecie, dup[
care procesul continu[ cu urm[torul mesaj.
              Figura 9 prezint[ un scenariu pentru transmisia lui p0=0 i p1=1, n care transmisia primului
bit a fost stricat[. Prima coloan[, marcat[ cu T numeroteaz[ paii. celelalte coloane sunt marcate cu
identificatorii de canal i arat[ valorile trimise prin acestea.

S=proc(x?Msg & sf!Msg & bs?Msg).                                   T  x  sf  fr  rb  bs y 
begin m,a:var Msg                                                                                                                                                     0  0
| x?m                                                                                                                                                                                                                                                   1      0
; forever                                                                                                                                                                                                                           2          E
  do sf!m; bs?a                                                                                                                                                                              3              0
   ; if a=1 then x?m fi                                                                                                           4                  0
  od                                                                                                                                                                                                                                                                    5      0
end                                                                                                                                                                                                                                                                           6          0
                                                                                                                                                                                                                                                                                                7                     0 
              Figura 7:                                                                                                                                 8              1
Programul 1 pentru expeditorul S                                                                             9                  1
                                                                                                                                                                                                                                                                                               10  1
R=proc(fr?Msg & rb!Msg & y!Msg).                                   11      1
begin m:var Msg                                                                                                                                                                             12          1
| forever                                                                                                                                                                                                                          13                     1
  do fr?m
   ; if m=E then rb!0                                                                                                                                                                                          Figura 9: 
     else y!m; rb!1                                                                                                                                            Protocol de transmitere pentru
     fi                                                                                                                                                                                                                                      p0=0,p1=1 cu o retransmitere a
  od                                                                                                                                                                                                                                                                   lui p0
end

              Figura 8: 
Programul 1 pentru destinatarul R 

SubProblema A:
              Protocolul prezentat mai sus nu lucreaz[ totdeauna aa cum dorim. Dai un exemplu pentru
a ar[ta aceasta, folosind o tabel[ similar[ celei din Figura 9.

SubProblema B:
              Modific[m programul expeditorului S i destinatarului R conform urm[torului protocol.
Expeditorul S (vezi Figura 10) indexeaz[ alternativ cu 0 i 1 fiecare bit primit de la P; n rest
opereaz[ similar ca nainte. Deci, un mesaj mTMsg (mcE) este un bit marcat: m.v este valoarea
bitului iar m.t marcajul.
                         Destinatarul R (vezi Figura 11) i rezerv[ o variabil[ local[ u{0,1} pentru a indica ce
marcaj ateapt[. La primirea unui mesaj via leg[tura de transmisie, destinatarul execut[ urm[toarele:
- dac[ mesajul este stricat, R trimite napoi 0;
- altfel, dac[ marcajul difer[ de u, trimite napoi 1 lui S, dar nu expediaz[ mesajul m lui C. Numai
dac[ un mesaj nestricat vine nsoit de un marcaj ateptat, el este predat mai departe lui C, iar
marcajul care va fi ateptat s[ vin[ n continuare se actualizeaz[.
- R ateapt[ un mesaj nou.
              Pogramele pentru P,L,C i modul de conectare r[mn la fel, exceptnd leg[tura de
transmisie care permite transmiterea de mesaje marcate (TMsg n loc de Msg).
              Dai un exemplu pentru a ar[ta c[ nici acest protocol nu lucreaz[ aa cum am fi dorit.
Folosii o tabel[ de aceeai form[ ca la Figura 9, marcnd cu o s[geat[ repetarea evenimentelor.

S=proc(x?Msg & sf!TMsg & bs?Msg).                                 R=proc(fr?TMsg & rb!Msg & y!Msg)

begin m:var TMsg & a:var Msg                                                                     begin m:var TMsg & u:var Nat
| m.t:=0; x?m.v                                                                                                                                                                             | u:=0
; forever                                                                                                                                                                                                                          ; forever
  do sf!m; bs?a                                                                                                                                                                               do fr?m
   ; if a=1                                                                                                                                                                                                    ; if m=E then rb!0
   then m.t:=1-m.t; x?m.v                                                                                                         else if m.t=u
     fi                                                                                                                                                                                                                                                then y!m.v; u:=1-u
  od                                                                                                                                                                                                                                                                             fi
end                                                                                                                                                                                                                                            od
                                                                                                                                                                                                                                                                                               end
              Figura 10                                                                                                                                                                                   Figura 11
Programul 2 pentru expeditorul S                                                                            Programul 2 pentru destinatarul R

SubProblema C:
              Modificai S i R pentru a face ca protocolul s[ lucreze corect. Modificai textul program al
lui S respectiv R situat ntre | i end. Nu este permis s[ se adauge variabile noi sau s[ se modifice
P,L sau C (sau modul lor de conectare). De asemenea, nu este permis[ inventarea unor construcii
noi de limbaj (instruciuni sau expresii).



                                            Soluii ale problemelor propuse

               IOI.1.
Algoritm:
              S[ presupunem c[ celulele libere se afl[ pe poziiile i,i+1; mutarea coninutului celulelor
de pe poziiile p,p+1 n celulele libere va fi notat[ prin pi.
              Se observ[ c[ pentru N=1 problema nu are sens (configuraia se reduce la dou[ c[sue
goale), iar pentru N=2, N=3 se poate s[ nu existe soluii; de exemplu;
B _ _ A (N=2),  B A _ _ B A (N=3).
Pentru N4 se poate construi un algoritm recursiv Greedy care s[ reduc[ problema la cazul N=4 i
configuraia A A _ _ x y B B. In acest moment sunt dou[ posibilit[i:
i) A A _ _ A B B B  - configuraie care verific[ condiia de terminare,
ii) A A _ _ B A B B - care, dup[ micarea 63 ncheie algoritmul.
Fie cells tabloul cu 2*N componente care trebuie sa fie aranjat i i poziia primei celule libere.
la un moment consider[m numai componentele aflate ntre poziiile [ns..nd]. Ideea este de a aduce
pe poziia ns un A, pe poziia nd un B i de a relua algoritmul pentru tabloul r[mas, cu componentele
din intervalul [ns+1,nd-1], ct timp acesta are cel puin 8 poziii.
Prima parte a algoritmului este deci:
Selecie(pd,i)
1. Cat timp pd8 executa
     1.1. ps:=2*N-pd+1;
     1.2. daca i=ps+1 atunci i+2i;i:=i+2;
     1.3. Dac[ cells(ps)c'A' atunci
         1.3.1. cauta cel mai din stanga jps+2 cu cells(j)='A';
         1.3.2. daca i=j+1 atunci i+2i;i:=i+2;
         1.3.3. daca cell(ps)='B' atunci psi;
         1.3.4. jps;
     1.4. Dac[ cell(pd)c'B' atunci
         1.4.1. cauta cel mai din dreapta kpd-2 
                  cu cell(k)='B';
         1.4.2. daca j+2=k atunci j-2j;j:=j-2;
         1.4.3. daca cell(pd)='A' atunci pd-1j;
         1.4.4. k-1pd-1
     1.5. Selectie(pd-1,k-1)
2. Se cauta in secventa cells(pd-6),..,cells(pd+1) daca cel mai din stanga
grup 'AA'; acesta se aduce pe poziiile cells(pd-6),cells(pd-5); altfel:
  - se aranjeaza ca prima celula libera sa fie pd-4 sau pd-3;
  - se aduce celula libera pe pozitia pd-5;
  - se cauta primul k>pd-5 cu cells(k)='A' i se face kpd-5;
3. Daca cells(pd)c'B' se permuta cells(pd,cells(pd+1) cu cel mai din stanga
grup 'BB' (care exista sigur) 
4. Revenire;
              Algoritmul principal efectueaz[ urm[toarele operaii:
1. Citete i verific[ datele de intrare i caut[ cazurile particulare.
2. Apeleaz[ Selectie(2*N,i);
3. Cerceteaz[ dac[ se obine situaia (ii); n caz afirmativ, se efectueaz[ o ultim[ deplasare;
4. Se scrie rezultatul.
Program:
var cells:array[1..50] of char;
    N,i,pfirstempty,nra,ptodo,wherefrom,moves:integer;
----------------------------------------------------
procedure mutare(pfirst:integer);
begin
cells[pfirstempty]:=cells[pfirst];
cells[pfirstempty+1]:=cells[pfirst+1];
pfirstempty:=pfirst;
cells[pfirstempty]:=' ';
cells[pfirstempty+1]:=' ';
moves:=moves+1;
end;
----------------------------------------------------
begin
readln(N);
pfirstempty:=2*N-1;
for i:=1 to 2*N-2 do read(cells[i]);
nra:=0;
ptodo:=1;
wherefrom:=3;
moves:=0;
while nra<n-1 do
    begin
    while cells[ptodo]='A' do
          begin
          ptodo:=ptodo+1;
          nra:=nra+1;
          end;
    if nra<n-1 then
       begin
       mutare(ptodo);
       while cells[wherefrom] in ['B',' '] do wherefrom:=wherefrom+1;
       mutare(wherefrom);
       end;
    end;
for i:=1 to 2*N do write(cells[i]);
writeln(' in ',moves,' moves');
end.

             IOI.2.
Algoritm:
S[ definim nti doi subalgoritmi. Primul, numit schimb, ntr-o grupare de patru celule, le
interschimb[ pe cele de pe diagonal[. La intrare sunt 4 celule aezate
                                                           A      B
                                                            C      D
unde, sau (i) (A)=(C)=0, sau (ii) (B)=(D)=0 (am notat cu (X) coninutul celulei (X)).
Algoritmul schimb(A,B,C,D) este:
1. Dac[ (B)=0 atunci salt la 3;
2. (D)C;(B)A;(C)B;(A)D;0A;0C;Revenire;
3. (A)D;(C)B;(D)C;(B)A;0B;0D;Revenire;
Al doilea sublagoritm, mutare, va permuta elementele dintr-o grupare de dou[ celule al[turate, din
care una conine 0;
mutare(A,B):
1. Dac[ (B)=0 atunci salt la 3:
2. (B)A;0B; Revenire;
3. (A)B;0A; Revenire;
Acum putem da un algoritm de rezolvare al problemei ioi.2.:
              Algoritm Joc_patratic:
Pas 1: Citete matricea A; 
Pas 2: Pentru fiecare k=1,14:
               2.1: Se determin[ poziia (i0,j0) unde trebuie s[ ajung[ k:
                k div 4  dac[ (k mod 4)c0
  i0= 
               (k div 4)+1   dac[ (k mod 4)=0
                                       k mod 4 dac[ (k mod 4)c0
                 j0
                                       4 dac[ (k mod 4)=0
              2.2: Se determin[ poziia (i,j) pe care se afl[ k n matricea A.
              2.3. In funcie de situaiile care apar, se trateaz[ unul din urm[toarele 9 subcazuri:
2.3.1. i<i0, j<j0;                      2.3.2. i<i0,j=j0;
2.3.3. i<i0,j>j0;                        2.3.4. i=i0,j<j0; 
2.3.5. i=i0,j=j0;                        2.3.6. i=i0,j>j0;
2.3.7. i>i0,j<j0;                        2.3.8. i>i0,j=j0;
2.3.9. i>i0,j>j0;
              Cazul de acceptare este 2.3.5, cnd se reia ciclul pasului 2. In celelalte situaii se caut[ ca
prin folosirea subalgoritmilor schimb i mutare, s[ se aduc[ matricea A la situaia 2.3.5. Vom
detalia algoritmul doar pentru primele trei cazuri, celelalte situaii fiind analoge.
2.3.1. Se aplic[ paii (a),(b),(c) ct timp i<i0,j<j0:
              a) Folosind sublagoritmul mutare se aduc cele dou[ zerouri pe poziiile (i+1,j) respectiv
(i,j+1);
              b) Se aplic[ subalgoritmul schimb pentru celulele:
                                            (i,j),(i,j+1),(i+1,j),(i+1,j+1).
              c) i+1i, j+1j.
In final se ajunge la unul din cazurile:2.3.2, 2.3.4, 2.3.5.
2.3.2. Se aplic[ paii (a),(b),(c) ct timp i<i0:
              a) Folosind sublagoritmul mutare se aduce unul din cele dou[ zerouri pe poziia (i+1,j0);
              b) Se aplic[ subalgoritmul mutare pentru celulele:(i,j0),(i+1,j0).
              c) i+1i.
In final se ajunge la cazul 2.3.5.
2.3.3. Se aplic[ paii (a),(b),(c) ct timp i<i0,j>j0:
              a) Folosind sublagoritmul mutare se aduc cele dou[ zerouri pe poziiile (i+1,j) respectiv
(i,j-1);
              b) Se aplic[ subalgoritmul schimb pentru celulele:
                                            (i,j),(i,j-1),(i+1,j),(i+1,j-1).
              c) i+1i, j-1j.
In final se ajunge la unul din cazurile: 2.3.2, 2.3.5, 2.3.6.

              Pentru minimizarea num[rului de aplic[ri ale subalgorimului mutare (care va conduce la
rezolvarea punctului 3 al problemei), se caut[ s[ se aduc[ pe poziia (i,j) acel 0 aflat pe poziia
(i',j') pentru care |i'-i|+|j'-j| este minim. 


              IOI.3.
Algoritm:
              Se poate folosi un vector PROGRAM(0..Endtime) iniializat cu zero.
In prima faz[ se aplic[ urm[torii pai;
Pentru fiecare i:=1,N
   Pentru fiecare j:=T1(i),T2(i)
      PROGRAM(j):=PROGRAM(j)+1.
Acum:
Pentru punctul 1: totul se reduce la a verifica condiia:
                                              PROGRAM(i)2 zi,0iEndtime
2) Se determin[ secvenele compacte din vectorul PROGRAM care au toate elementele 0 sau 1;
3) Se introduce un vector SUPL(0..Endtime) care are c1 pe o poriune de lungime Lenght
ncepnd cu poziia primului element strict mai mic dect 2 din PROGRAM, 0 n rest.
Se face PROGRAM:=PROGRAM+SUPL (component[ cu component[);
Dac[ noul vector PROGRAM mai are elemente <2, algoritmul (relativ la acest punct) se reia.
In final, num[rul de paznici suplimentari este egal cu num[rul de relu[ri ale algoritmului. 
4) Se folosete vectorul PROGRAM obinut la pasul 1.
Dac[ 0iEndtimePROGRAM(i)/(Endtime+1)<2, r[spunsul este negativ (sunt necesari paznici
suplimentari). Altfel:
-               Se alege un paznic p prin scoaterea c[ruia vectorul PROGRAM are cele mai puine elemente
>2; se lucreaz[ cu noul vector PROGRAM. 
-               Se construiete un vector SUPL(0,Endtime) cu 1 pe T2(p)-T1(p) poziii  0 n rest,
astfel nct s[ se meximizeze num[rul de elemente 2 din vectorul PROGRAM:=PROGRAM+SUPL.
Se modific[ corespunz[tor elementele T1(p),T2(p).
              Procedeul se reia pn[ cnd PROGRAM(i)2 zi,0iEndtime.
               Program:
type leg=^pereche;
     pereche=record
             p1,p2:integer;
             end;
     pauz=record
          inceput,sfarsit:integer;
          end;
var EndTime,Lngth,N,i,durata:integer;
    T1,T2:array[1..100] of integer;
    pauza:pauz;
--------------------------------------------------
function sunt_paznici(timp:integer):leg;
{ intoarce 2 paznici daca exista cel putin 2 paznici la momentul timp.
           Daca nu, intoarce 0 }
var result:leg;
    i:integer;
begin
result^.p1:=0;
result^.p2:=0;
i:=1;
while (i<=N) and (result^.p2=0) do
      begin
      if (T1[i]<=timp) and (T2[i]>=timp) then
         if result^.p1<>0 then result^.p2:=i
                          else result^.p1:=i;
      i:=i+1;
      end;
sunt_paznici:=result;
end;
--------------------------------------------------
begin
readln(EndTime,N);
for i:=1 to n do readln(t1[i],t2[i]);
durata:=0;
pauza.inceput:=0;
pauza.sfarsit:=0;
for i:=1 to EndTime do
    if sunt_paznici(i)^.p2=0 then
       begin
       if durata=0 then writeln('Nu exista cel putin 2 paznici in
fiecare moment.');
       if pauza.inceput=0 then pauza.inceput:=i;
       durata:=durata+1;
       end
    else if pauza.inceput<>0 then
            begin
            pauza.sfarsit:=i-1;
           writeln('(',pauza.inceput:3,',', pauza.sfarsit:3,')');
            pauza.inceput:=0;
            pauza.sfarsit:=0;
            end;
if pauza.inceput<>0 then
   begin
   pauza.sfarsit:=i;
  writeln('(',pauza.inceput:3,',', pauza.sfarsit:3,')');
   pauza.inceput:=0;
   pauza.sfarsit:=0;
   end;
if durata=0 then writeln('Exista cel putin 2 paznici in fiecare
moment.')
else begin
     readln(Lngth);
     writeln('Mai sunt necesari ',trunc(durata/Lngth)+1:3,' paznici.');
     end;
end.
                         IOI.4.
Algoritm:
               A. Se construiesc la fiecare pas lanuri de lungime p n felul urm[tor:
1. Dac[ p=1 atunci exist[ un singur lan care const[ din poziia (i1,j1), citit[ la intrare;
2. S[ presupunem c[ ncepem pasul p (p2) avnd construite k lanuri, fiecare de lungime p-1;
Pentru fiecare lan t (1tk) care se termin[ cu poziia (it,jt):
              2.1. Se determin[ toate poziiile (u,v) la care se poate ajunge din (it,jt)
aplicnd regulile din problem[;
              2.2. Se elimin[ toate poziiile care exist[ deja n lan; fie s num[rul poziiilor r[mase;
              2.3. Dac[ s=0, lanul t se elimin[;
              2.4. Altfel (s>0) lanul t se nlocuiete cu s lanuri obinute din t prin ad[ugarea la sfrit
a ctei uneia din cele s poziii;
              2.5. Dac[ p<25, se face p+1p i se reia pasul 2.
3. Pentru fiecare lan se construiete cte un tablou astfel:
              Dac[ (i,j) este al k-lea element al lanului, se scrie num[rul k pe poziia (i,j) din
tablou.
              Pentru punctul (B), se fac urm[toarele modific[ri:
Tot algoritmul anterior se introduce n ciclul dublu:
Pentru i1:=1 pn[ la 5
               Pentru j1:=1 pn[ la 5
              A;
              In plus pasul 3 este nlocuit cu:
3'. Se scrie pe poziia (i1,j1) num[rul de lanuri obinute.
Program:
const a:array [1..8,1..2] of
integer=((3,0),(-3,0),(0,3),(0,-3),(2,2),(2,-2),(-2,2),(-2,-2));
type grila=array[1..5,1..5] of byte;
var g,x:grila;
    i,j,nr_matrici:integer;
---------------------------------------------------procedure scrie(g:grila);
var i,j:integer;
begin
for i:=1 to 5 do
    begin
    for j:=1 to 5 do write(g[i,j]:4);
    writeln;
    end;
writeln;
end;
---------------------------------------------------procedure
calc(t,x,y:integer;actiune:boolean);
{ genereaza matricile cu t pe pozitia (x,y) prin metoda backtracking. Daca
actiune este true, le scrie in fisier, daca nu, doar intoarce numarul lor in
variabila nr_matrici }
var i:integer;
begin
if g[x,y]=0 then
   if t<25 then
      begin
      g[x,y]:=t;
      for i:=1 to 8 do
          if (x+a[i,1]<=5) and (y+a[i,2]<=5) and (x+a[i,1]>0) and (y+a[i,2]>0)
then
             calc(t+1,x+a[i,1],y+a[i,2],actiune);
      g[x,y]:=0;
      end
   else if t=25 then
           begin
           g[x,y]:=t;
           if actiune then scrie(g)
                      else inc(nr_matrici);
           g[x,y]:=0;
           end;
end;
---------------------------------------------------begin
assign(output,'output.io4');
rewrite(output);
for i:=1 to 5 do for j:=1 to 5 do { initializeaza matricile la 0 }
    begin
    g[i,j]:=0;
    x[i,j]:=0;
    end;
readln(i,j); { citeste pozitia termenului 1 }
calc(1,i,j,TRUE); { genereaza matricile }
for i:=1 to 5 do
    for j:=i to 5 do
        if x[i,j]=0 then
           begin
           nr_matrici:=0;
           calc(1,i,j,FALSE);
           x[i,j]:=nr_matrici;
           { acelasi rezultat se va obtine si pentru datele de intrare
(6-i,6-j) }
           x[6-i,6-j]:=nr_matrici;
           end;
scrie(x);
close(output);
end.

             IOI.5.
Algoritm:
Pentru gensterm se poate da un algoritm recursiv care folosete ca variabile globale n (citit la
intrare), i mulimile L,L':
gensterm(k):
  1. Dac[ k=1 atunci L':={s}; salt la 4
              altfel gensterm(k-1);
  2. L':=H;
  3. Pentru fiecare L
        Pentru i:=1,k-1
       Fie scrierea =sy unde  conine i-1 s-uri;
           L':=L'B{(ssy};
  4. L:=L'; 
     se scrie L n fiierul de iesire TERM_k;
  5. Dac[ k=n atunci Stop altfel Revenire.

              Un s-termen constituie de fapt scrierea infixat[ a unei expresii de tip aritmetic avnd ca
operand s i ca operator (. Cum reprezentarea natural[ a scrierii infixate este aceea prin arbori binari,
putem lua arborii binari ca reprezentare.
              Atunci printterm constituie de fapt parcurgerea infixat[ a unui arbore binar (algoritm
cunoscut din manualul de liceu), iar pentru readterm putem da diveri algoritmi; de exemplu;
readterm()
Intrare: s-termenul ;
ieire: Arborele binar a c[rui parcurgere infixat[ este ;
Iniial T:={s,s,..,s}, num[rul de s-uri fiind egal cu cel din ;
Not[m cu N(x) num[rul de paranteze din expresia x:
1. Pentru i:=1,N()
   1.1. Dac[ N()=0 atunci Stop;
   1.2. Fie =(yzy cu N(yzy)=0 (se pune n eviden[ ultima parantez[);
          T:=(T-{y,z})B{p} unde p este un nume nou dat arborelui 
                                                                       (

                                       y z
           :=py;
2. Se scrie arborele aflat n T.
              O reducere nseamn[ o echilibrare de arbori dup[ regula:

                                                                       (      (

                                       ( C                                                 ((

               (                        B         =>      A                        CB                       C

s                                     A

                         O normalizare const[ n aplicarea ct timp este posibil a urm[torului algoritm:
Fie =(((sABCy unde:
   - A,B,C sunt s-termeni;
   - In ABCy nu exist[ ((( ca subcuvnt;
Atunci,  se nlocuiete cu :=((AC(BCy.

              Ali algoritmi pot fi g[sii prin analiza programului urm[tor sau a programului dat de conf.
dr. Horia Georgescu n GI/2 1991.
Program:
uses crt;
type vector=array[1..10] of byte;
     nod=^celula;
     celula=record
            radacina:char;
            stanga,dreapta:nod;
            end;
var n,i:byte;
    coef:vector;
    ultimul:boolean;
    start,start2:nod;
    s:string[20];
  curent,nr_termeni,nr_normalizari,
      nr_normalizati:integer;
--------------------------------------------------
function height(n:nod):byte;
var r:byte;
    crt:nod;
begin
crt:=n;
r:=0;
while crt^.radacina='(' do
      begin
      inc(r);
      crt:=crt^.stanga;
      end;
height:=r;
end;
---------------------------------------------------procedure printterm(var
n:nod);
begin
s:=s+n^.radacina;
inc(curent);
if n^.radacina='(' then
   begin
   printterm(n^.stanga);
   printterm(n^.dreapta);
   end;
end;
---------------------------------------------------procedure normalize(var
n,na:nod);
var h:byte;
    tmp,crt:nod;
begin
if n^.radacina='(' then
   begin
   normalize(n^.stanga,n);
   normalize(n^.dreapta,n);
   if height(n)=3 then
      begin
      inc(nr_normalizari);
      tmp:=n^.stanga;
      n^.stanga:=n^.stanga^.dreapta;
      n^.stanga^.stanga^.stanga:=
 n^.stanga^.stanga^.dreapta;
      n^.stanga^.stanga^.dreapta:=n^.dreapta;
      tmp^.dreapta:=n;
      if na^.dreapta=n then na^.dreapta:=tmp
      else na^.stanga:=tmp;
      end;
   end;
end;
---------------------------------------------------procedure readterm(var
n:nod);
begin
new(n);
n^.radacina:=s[curent];
inc(curent);
if n^.radacina='(' then
   begin
   readterm(n^.stanga);
   readterm(n^.dreapta);
   end;
end;
---------------------------------------------------procedure
genterm(coef:vector;x:integer);
var i,j:byte;
    gata:boolean;
begin
gata:=true;
for i:=2 to n-1 do if coef[i]<>coef[i-1]+1 then gata:=false;
if gata=true then
   ultimul:=gata;
 if (x<n-1) and (not ultimul) then
   for i:=coef[x] to coef[x]+2 do
       begin
       if not ultimul then
          begin
          coef[x+1]:=i;
          genterm(coef,x+1);
          end;
       end
 else if x=n-1 then
    begin
    s:='';
    for i:=1 to n-2 do
        begin
        s:=s+'(';
        for j:=coef[i] to coef[i+1]-1 do s:=s+'s';
        end;
    s:=s+'(';
    for i:=coef[n-1] to n do s:=s+'s';
    curent:=1;
    write(s,'   ');
    s:='';
    curent:=1;
    readterm(start);
    start2^.stanga:=start;
    nr_normalizari:=0;
    normalize(start,start2);
    printterm(start2^.stanga);
    if nr_normalizari in [30,0] then 
       s:='NOT NORMALIZED'
    else inc(nr_normalizati);
    inc(nr_termeni);
    write(s);
    if not(nr_normalizari in [30,0]) then writeln
 (' normalizat in ',nr_normalizari,' reduceri.')
    else writeln;
    end;
end;
---------------------------------------------------begin
clrscr;
assign(output,'output.io5');
rewrite(output);
readln(n);
ultimul:=false;
for i:=1 to n-1 do coef[i]:=1;
nr_normalizati:=0;
nr_termeni:=0;
genterm(coef,1);
writeln(nr_termeni,' termeni, dintre care ',nr_normalizati,' normalizati.');
end.

             IOI. 6
Algoritm:
Ideea este de a folosi un ablon - un vector binar care constituie soluia unei restricii (se marcheaz[
cu 1 poziia unei insule i cu 0 absena ei), cu proprietatea c[ num[rul asociat este minim.
De exemplu, pentru restricia 1 2 sunt posibile trei abloane: (0 0 1 0 1 1),(0 1 0 0 1 1),
(1 0 0 0 1 1). Orice alt[ configuraie posibil[ a liniei se poate obine din aceste abloane prin
translatare spre stnga ct timp nu se pierde nici un 1; aritmetic, aceasta este echivalent[ cu nmulirea
cu 2 a num[rului asociat ablonului.
Este foarte simplu de a construi algoritmi care:
i) Plecnd de la o restricie, s[ construiasc[ abloanele ei;
ii) Pentru fiecare ablon, s[ genereze num[rul binar asociat precum i translat[rile sale.
Algoritmul de rezolvare al problemei va lucra atunci astfel:
1. Se citete n (ordinul reelei);
2. Pentru i:=1,n
   2.1. Se citete restricia i (pentru linii);
   2.2. Se construiesc numerele care formeaz[ abloanele; fie p1,..,pk
reprezentarea lor n zecimal;
   2.3. Se construiete mulimea Li=B1jk{t*pj|t=1,2,..,r, (r+1)*pj>2n-1}
(cu ajutorul a dou[ cicluri);
3. Pentru i:=1,n
   3.1. Se citete restricia i (pentru coloane);
   3.2. Se construiesc numerele care formeaz[ abloanele; fie q1,..,qk
reprezentarea lor n zecimal;
   3.3. Se construiete mulimea Ci=B1jk{t*qj|t=1,2,..,r, (r+1)*qj>2n-1}
(cu ajutorul a dou[ cicluri);
 4. Printr-un algoritm de tip backtracking se determin[ dac[ exist[
dou[ matrici patrate L=(b1 b2 .. bn)T, C=(c1 c2 .. cn)T unde bi este
scrierea n binar a unui num[r din Li, ci este scrierea n binar a unui
num[r din Ci, cu proprietatea c[ L(i,j)=C(j,i) zi,j 1i,jn.
In caz afirmativ, L este chiar soluia problemei. Altfel, nu exist[
soluie.
              Este interesant faptul c[ restricia din problem[ 1N8 permite un algoritm foarte uor de
implementat n C, unde este posibil de lucrat cu bii. Aloritmul de sus se implementeaz[ asociind cte
un octet fiec[rei restricii.
Program:
uses crt;
type line=array[1..9] of byte;
     info_line=record
               a:array[1..4] of byte;
               islands,stars:byte;
               end;
var sea:array[1..8] of line;
    linii,coloane:array[1..8] of info_line;
    i,j,N:integer;
    gasit,last,sfarsit:boolean;
    input,output:text;
---------------------------------------------------procedure next_line(var
l:line;s,is:integer);
var i,stars,islands:integer;
    on:boolean;
    input:text;
begin
last:=false;
l[N+1]:=0;
repeat
      inc(l[1]);
      stars:=0;
      islands:=0;
      on:=false;
      for i:=1 to N do
          begin
          if l[i]=2 then
             begin
             l[i]:=0;
             inc(l[i+1]);
             end;
          if l[i]=1 then
             begin
             inc(stars);
             if not on then on:=true;
             end;
          if on and ((l[i]=0) or (i=N)) then
             begin
             on:=false;
             inc(islands);
             end;
          end;
until (stars=s) and (islands=is);
{for i:=1 to N do write(l[i],' ');
write('  -  ',stars,' ',islands);}
last:=(l[N+1]<>0);
end;
---------------------------------------------------procedure read_info(var
linii:info_line);
var i:integer;
    ends:boolean;
begin
i:=1;
ends:=false;
while (i<=N) and (not ends) do
    begin
    read(input,linii.a[i]);
    ends:=(linii.a[i]=0);
    linii.stars:=linii.stars+linii.a[i];
    inc(i);
    end;
readln(input);
linii.islands:=i-2;
{for i:=1 to N do write(linii.a[i],' ');
writeln('  -  ',linii.stars,' ',linii.islands);}
end;
---------------------------------------------------procedure write_solution;
var i,j:integer;
begin
writeln(output);
for i:=1 to N do
    begin
    for j:=1 to N do write(output,sea[i][j],' ');
    writeln(output);
end;
---------------------------------------------------function vcoloane:boolean;
var ok,on:boolean;
    i,j,stars,stars1,islands:integer;
begin
i:=1;
ok:=true;
while (i<=N) and ok do
      begin
      islands:=0;
      stars1:=0;
      stars:=0;
      on:=false;
      for j:=1 to n do
          begin
          if sea[j][i]=1 then
             begin
             inc(stars);
             on:=true;
             end;
          if on and ((sea[j][i]=0) or (j=N)) then
             begin
             inc(islands);
         if coloane[i].a[islands]<>stars-stars1
             then ok:=false;
             on:=false;
             stars1:=stars;
             end;
          end;
      if (islands<>coloane[i].islands) or
 (stars<>coloane[i].stars) then ok:=false;
      inc(i);
      end;
vcoloane:=ok and (i<=N+1);
end;
---------------------------------------------------procedure arrange;
var i,j:integer;
begin
next_line(sea[1],linii[1].stars,linii[1].islands);
for i:=1 to N do
    if last then
       begin
       for j:=1 to N do sea[i][j]:=0;
 next_line(sea[i],linii[i].stars,linii[i].islands);
       next_line(sea[i+1],linii[i+1].stars,
   linii[i+1].islands);
       if i=N then sfarsit:=true;
       end;
end;
---------------------------------------------------begin
clrscr;
assign(input,'input');
assign(output,'output.io6');
rewrite(output);
reset(input);
while not eof(input) do
      begin
      gasit:=false;
      readln(input,N);
      for i:=1 to N do
          begin
          read_info(linii[i]);
          for j:=1 to N do sea[i][j]:=0;
          end;
      for i:=1 to N do read_info(coloane[i]);
      sfarsit:=false;
      repeat
            arrange;
            if vcoloane then
               begin
               gasit:=true;
               write_solution;
               end;
      until sfarsit;
      writeln(output);
      if not gasit then writeln(output,'No map');
      readln(input);
      end;
close(input);
close(output);
end.

             IOI. 7
Algoritm:
??????????????????????????
Program:
uses crt;
label start;
type cerinte=record
             zile,resurse:integer;
             end;
     stiri=record
           nr_alpinist,unit_pe_zi,max_unit,putere:integer;
           end;
var club:array[1..20] of stiri;
    lista:array[1..20] of cerinte;
    necesar,ramas,distanta,curent,i,j,nr_membri,total,nr_alpinisti:byte;
    s:stiri;
    imposibil,gasit:boolean;
    c:char;

function cat_trebuie(necesar:cerinte;alpinist:integer):integer;
{ intoarce numarul de resurse necesare alpinistului alpinist ca sa
indeplineasca
  conditiile puse de necesar }
begin
cat_trebuie:=necesar.zile*club[alpinist].unit_pe_zi+necesar.resurse;
end;

function min(x,y:integer):integer;
begin
min:=x;
if y<x then min:=y;
end;

begin
clrscr;
start:
write('Zile pentru a ajunge in varf : ');
readln(distanta);
write('Numarul membrilor clubului : ');
readln(nr_membri);
for i:=1 to nr_membri do
    begin
    club[i].nr_alpinist:=i;
    write('Maximul de resurse pentru alpinistul ',i,' : ');
    readln(club[i].max_unit);
    write('Consumul zilnic al alpinistului ',i,' : ');
    readln(club[i].unit_pe_zi);
    club[i].putere:=club[i].max_unit div club[i].unit_pe_zi;
    end;
for i:=1 to nr_membri do
    for j:=nr_membri downto i+1 do
        if club[j].putere>club[j-1].putere then
           begin
           s:=club[j];
           club[j]:=club[j-1];
           club[j-1]:=s;
           end;
curent:=1;
imposibil:=false;
gasit:=false;
distanta:=4;
ramas:=0;
total:=0;
nr_alpinisti:=0;
repeat
      necesar:=ramas+distanta*club[curent].unit_pe_zi;
      { necesar reprezinta cantitatea de resurse disponibila care ramane dupa
urcare }
      if necesar>club[curent].max_unit then imposibil:=true
      else begin
           write('Alpinistul ',club[curent].nr_alpinist,' cara ');
           inc(nr_alpinisti);
           if
necesar<=club[curent].max_unit-distanta*2*club[curent].unit_pe_zi-ramas then
              begin
              write(distanta*2*club[curent].unit_pe_zi+ramas);
              total:=total+distanta*2*club[curent].unit_pe_zi+ramas;
              end
           else
              begin
              write(club[curent].max_unit);
              total:=total+club[curent].max_unit;
              end;
           writeln(' si coboara dupa ',distanta);
           distanta:=distanta*2-(club[curent].max_unit-ramas) div
club[curent].unit_pe_zi;
           ramas:=distanta div club[curent].unit_pe_zi;
           if distanta<=0 then gasit:=true;
           end;
      inc(curent);
until imposibil or gasit;
if not imposibil then writeln(nr_alpinisti,' necesari; cantitate totala
',total)
                 else writeln('Urcare imposibila');
writeln;
repeat
      write('Alte date (Y/N) ');
      readln(c);
      c:=upcase(c);
until c in ['Y','N'];
if c='Y' then goto start;
end.

             IOI. 8
Algoritm:
Pentru a facilita calculele, vom nota culoarea rou cu 0, alb cu 1 i albastru cu 2.
Algoritmul este iterativ; caut[ din toate situaiile posibile acea t[ietur[ s care duce la maximizarea
valorii lui M.
              Am introdus trei subalgoritmi:
numar(colier,k) - calculeaz[ num[rul k de m[rgele de aceeai culoare situate pe colier, parcurs
                                     spre dreapta;
revers(colier) - consider[ vectorul colier scris n ordine invers[;
ciclic(colier) - efectueaz[ permutarea ciclic[ a m[rgelelor colierului; este echivalent cu                                       aciunea de t[iere a colierului dup[ m[rgica urm[toare.

1. M:=1; s:=0;
2. pentru i:=1,n-1
     2.1. numar(colier,p);
     2.2. numar(revers(colier),q);
     2.3. Dac[ M<p+q atunci M:=p+q, s:=i;
     2.4. Dac[ M=n atunci salt la 3;
     2.5. colier:=ciclic(colier);
3. Scrie M,(s,s+1).
numar(colier,k)
1. a:=colier(1); i:=2;
2. Dac[ ac1 atunci
     2.1. cat timp (|colier(i)-a|1) i (in)
                  i:=i+1;
     2.2. k:=i-1; Revenire;
3. Dac[ |colier(i)-a|=1 atunci a:=colier(i);
4. i:=i+1;
5. Dac[ (a=1) i (in) atunci salt la 3
                       altfel salt la 2.1.

Program:
uses crt;
var s:string[100];
    suma1,suma2,i,sumamax,taietura,solutie:integer;
begin
clrscr;
assign(input,'input.io8');
assign(output,'output.io8');
rewrite(output);
reset(input);
while not eof(input) do
      begin
      readln(input,s);
      taietura:=1;
      sumamax:=0;
      solutie:=taietura;
      while taietura<=length(s) do
            begin
            i:=taietura;
            suma1:=0;
            while ((s[i]='w') or (s[i]=s[taietura])) and not((suma1<>0) and
(i=taietura)) do
                  begin
                  dec(i);
                  inc(suma1);
                  if i<1 then i:=length(s);
                  end;
            suma2:=0;
            i:=taietura+1;
            while ((s[i]='w') or (s[i]=s[taietura+1])) and not((suma2<>0) and
(i=taietura+1)) do
                  begin
                  inc(i);
                  inc(suma2);
                  if i>length(s) then i:=1;
                  end;
            if suma1+suma2>sumamax then
               begin
               sumamax:=suma1+suma2;
               solutie:=taietura;
               end;
            inc(taietura);
            end;
      writeln(output,s);
      writeln(output,sumamax,' between ',solutie,' and ',solutie+1);
      writeln(output);
      end;
end.

             IOI. 9
Algoritm:
Datele problemei se introduc ntr-o matrice actiuni(n,n), definit[ astfel:
actiuni(i,j)=procentul de aciuni ale companiei j deinut de compania i
actiuni(i,i)=
  Algoritmul consider[ c[ n momentul n care compania i controleaz[ compania j, aceasta va ceda
toate aciunile sale lui i; formal aceasta se va reprezenta prin adunarea liniei j la linia i.
              pentru fiecare linie algoritmul se reia cu matricea actiuni iniial[.

1. pentru i:=1,n
   1.1. j:=0;

   1.2. repeta 
          1.2.1. j:=j+1;
          1.2.2. dac[ j>n atunci salt la 1.7.
        pana cand actiuni(i,j)[51,100]
   1.3. scrie 'i controleaza j'
   1.4. pentru k:=1,n
           actiuni(i,k):=actiuni(i,k)+actiuni(j,k)
   1.5. actiuni(i,j)=
   1.6. salt la 1.1.
   1.7. se reface matricea actiuni initiala
2. Stop
Program:
var grila:array[1..100,1..100] of byte;
    studiat:array[1..100,1..100] of boolean;
    input,output:text;
    i,j,nr,a,b,x:integer;
    repeta:boolean;
begin
assign(input,'input.io9');
assign(output,'output.io9');
reset(input);
rewrite(output);
while not eof(input) do
      begin
      nr:=0;
      for i:=1 to 100 do for j:=1 to 100 do grila[i,j]:=0;
      for i:=1 to nr do for j:=1 to nr do studiat[i,j]:=false;
      while (not eoln(input)) and (not eof(input)) do
            begin
            readln(input,a,b,x);
            inc(nr);
            grila[a,b]:=x;
            end;
      repeat
            repeta:=false;
            for i:=1 to nr do
                for j:=1 to nr do
                    if (i<>j) and (grila[i,j]>=50) and (not studiat[i,j]) then
                       begin
                       for x:=1 to nr do grila[i,x]:=grila[i,x]+grila[j,x];
                       studiat[i,j]:=true;
                       repeta:=true;
                       end;
      until not repeta;
      for i:=1 to nr do for j:=1 to nr do if (i<>j) and (grila[i,j]>=50) then
writeln(output,i,' ',j);
      if eoln(input) then readln(input);
      writeln(output);
      end;
close(input);
close(output);
end.

             IOI. 10
Algoritm:
Algoritmul este iterativ i lucreaz[ dup[ urm[toarea idee:
- coloreaz[ foaia de hrtie prin suprapunerea culorilor n ordinea citirii dreptunghiurilor;
- caut[ o celul[ colorat[; cnd a depistat-o, o recoloreaz[ ntr-o culoare nou[ i ncepe colorarea
vecinilor din aceeai figur[. Atragem atenia aici asupra a dou[ situaii limit[:
i) este posibil s[ existe un dreptunghi suprapus care s[ aib[ culoarea hrtiei;
ii) dup[ recolorarea unei celule, se rencepe c[utarea vecinilor celulei anterioare 9altfel sunt cazuri
cnd se pierd vecini).
O formalizare a acestei descrieri este:
1. citeste a,b,N; se defineste tabloul tab[-a/2..a/2,-b/2..b/2]
2. se umple tot tabloul tab cu 1 (culoarea alba a hartiei);
3. pentru i:=1,N
   3.1. citeste linia i: x1(i),y1(i),x2(i),y2(i),c(i)

   3.2. pentru k:=x1(i),x2(i)
           pentru j:=y1(i),y2(i)
              tab(k,j):=c(i)
   3.3. x1(0):=-a/2;x2(0):=a/2;y1(0):=-b/2;y2(0):=b/2;c(0):=1
4. pentru i:=0,N
    4'. pentru j1:=x1(i),x2(i)
           pentru j2:=y1(i),y2(i)
             4.1. daca tab(j1,j2)=c(i) atunci
                4.1.1. tab(j1,j2):=65+c(i); arie:=1
                4.1.2. pentru k1:=x1(i),x2(i)
                          pentru k2:=y1(i),y2(i)
                       daca |tab(k1,k2)-vecin(tab(k1,k2)|=65 atunci
                         arie:=arie+1;
                         tab(k1,k2):=65+c(i);vecin(tab(k1,k2)):=65+c(i)
                         k1:=k1-1;k2:=k2-1
                4.1.3. scrie c(i),arie
5. Stop
vecin(tab(i,j)) determina toate celulele vecine pe orizontal[ sau verticala cu tab(i,j),
situate n intyeriorul foii de hrtie.
Program:
uses crt;
type legatura=^dreptunghi;
     dreptunghi=record
                x1,y1,x2,y2,culoare:integer;
                urm:legatura;
                end;

var curent1,start,curent:legatura;
    input:text;
    arie,fcurent,primaf,numar_figuri,a,b,n,i,v:integer;
    d:dreptunghi;
    f:array[1..100] of legatura;
    intersecteaza:boolean;

function value(d1,d2:dreptunghi):integer;
var result:integer;
begin
result:=0;
if (d1.x1<=d2.x2) and (d1.x1>=d2.x1) then inc(result);
if (d1.x2<=d2.x2) and (d1.x2>=d2.x1) then inc(result);
if (d1.y1<=d2.y2) and (d1.y1>=d2.y1) then inc(result);
if (d1.y2<=d2.y2) and (d1.y2>=d2.y1) then inc(result);
if result=1 then result:=0;
value:=result;
end;

function in_point(d:dreptunghi;x,y:integer):boolean;
begin
in_point:=((x>=d.x1) and (x<=d.x2) and (y>=d.y1) and (y<=d.y2));
end;

function in_point_x(d:dreptunghi;x:integer):boolean;
begin
in_point_x:=((x>=d.x1) and (x<=d.x2));
end;

function in_point_y(d:dreptunghi;y:integer):boolean;
begin
in_point_y:=((y>=d.y1) and (y<=d.y2));
end;

procedure put_rectangle(x1,y1,x2,y2,c:integer);
var d:legatura;
begin
new(d);
d^.x1:=x1;
d^.y1:=y1;
d^.x2:=x2;
d^.y2:=y2;
d^.urm:=start;
d^.culoare:=c;
start:=d;
end;

procedure imparte(d1,d2:dreptunghi;n:integer);
var c:integer;
begin
c:=d2.culoare;
if n<>0 then
   begin
   if in_point(d2,d1.x1,d1.y1)then
      begin
      put_rectangle(d2.x1,d1.y1,d1.x1,d2.y2,c);
      put_rectangle(d2.x1,d2.y1,d2.x2,d2.y1,c);
      if n=3 then if in_point_x(d2,d1.x2) then
put_rectangle(d1.x2,d1.y1,d2.x2,d2.y2,c)
                  else if in_point_y(d2,d1.y2) then
put_rectangle(d1.x1,d1.y2,d2.x2,d2.y2,c);
      if n=4 then
         begin
         put_rectangle(d1.x1,d1.y2,d2.x2,d2.y2,c);
         put_rectangle(d1.x2,d1.y1,d2.x2,d1.y2,c);
         end;
      end
   else if in_point(d2,d1.x1,d1.y2) then
           begin
           put_rectangle(d2.x1,d2.y1,d1.x1,d2.y2,c);
           put_rectangle(d2.x1,d1.y2,d2.x2,d2.y2,c);
           if n=3 then if in_point_x(d2,d1.x2) then
put_rectangle(d1.x2,d2.y1,d2.x2,d1.y2,c)
                       else if in_point_y(d2,d1.y1) then
put_rectangle(d1.x1,d2.y1,d2.x2,d1.y1,c);
           if n=4 then
              begin
              put_rectangle(d1.x1,d2.y1,d2.x2,d1.y1,c);
              put_rectangle(d1.x2,d1.y1,d2.x2,d1.y2,c);
              end;
           end
   else if in_point(d2,d1.x2,d1.y1) then
        begin
        put_rectangle(d2.x1,d2.y1,d2.x2,d1.y1,c);
        put_rectangle(d1.x2,d1.y1,d2.x2,d2.y2,c);
        if n=3 then if in_point_x(d2,d1.x1) then
put_rectangle(d2.x1,d1.y1,d1.x1,d2.y2,c)
                    else if in_point_y(d2,d1.y2) then
put_rectangle(d2.x1,d1.y2,d1.x2,d2.y2,c);
        if n=4 then
           begin
           put_rectangle(d2.x1,d1.y1,d1.x1,d2.y2,c);
           put_rectangle(d1.x1,d1.y2,d1.x2,d2.y2,c);
           end;
        end
   else if in_point(d2,d1.x2,d1.y2) then
        begin
        put_rectangle(d2.x1,d1.y2,d2.x2,d2.y2,c);
        put_rectangle(d1.x2,d2.y1,d2.x2,d1.y2,c);
        if n=3 then if in_point_x(d2,d1.x1) then
put_rectangle(d2.x1,d2.y1,d1.x1,d1.y2,c)
                    else if in_point_y(d2,d1.y1) then
put_rectangle(d2.x1,d2.y1,d1.x2,d1.y1,c);
        if n=4 then
           begin
           put_rectangle(d2.x1,d2.y1,d1.x2,d1.y1,c);
           put_rectangle(d2.x1,d1.y1,d1.x1,d1.y2,c);
           end;
        end;
   end;
end;

procedure sterge(l:legatura);
var c:legatura;
begin
c:=start;
while c^.urm<>l do c:=c^.urm;
l:=c^.urm^.urm;
dispose(c^.urm);
c^.urm:=l;
end;

begin
clrscr;
assign(input,'input.i10');
reset(input);
readln(input,a,b,n);
start:=nil;
for i:=1 to n do
    begin
    readln(input,d.x1,d.y1,d.x2,d.y2,d.culoare);
    { daca dreptunghiul pus intersecteaza vreun alt dreptunghi }
    curent:=start;
    while curent<>nil do
          begin
          v:=value(d,curent^);
          if v<>0 then
             begin
             { imparte in dreptunghirile vizibile }
             imparte(d,curent^,v);
             { si sterge dreptunghiul care a fost acoperit }
             sterge(curent);
             end;
          curent:=curent^.urm;
          end;
    { adauga dreptunghiul la lista }
    put_rectangle(d.x1,d.y1,d.x2,d.y2,d.culoare);
    end;
{ construieste figurile }
curent:=start;
numar_figuri:=0;
for i:=1 to 100 do f[i]:=nil;
while curent<>nil do
      begin
      { testeaza daca dreptunghiul curent intersecteaza vreo figura }
      fcurent:=1;
      primaf:=0;
      while f[fcurent]<>nil do
            begin
            { pentru toate dreptunghiurile din figura }
            curent1:=f[fcurent];
            intersecteaza:=false;
            while (curent1<>nil) and (not intersecteaza) do
                  begin
                  if (value(curent1^,curent^)<>0) and
(curent1^.culoare=curent^.culoare) then intersecteaza:=true
                  else curent1:=curent1^.urm;
                  end;
            { daca face parte din figura fcurent }
            if intersecteaza then
               begin
               { daca este prima figura intersectata }
               if primaf=0 then
                  begin
                  { adauga dreptunghiul la figura }
                  curent1:=f[fcurent];
                  new(f[fcurent]);
                  f[fcurent]^:=curent^;
                  f[fcurent]^.urm:=curent1;
                  primaf:=fcurent;
                  end
               else
                  begin
                  { daca nu este prima figura intersectata }
                  { adauga figura curenta la prima ficura intersectata }
                  curent1:=f[primaf];
                  while curent1^.urm<>nil do curent1:=curent1^.urm;
                  curent1^.urm:=f[fcurent];
                  f[fcurent]:=nil;
                  dec(numar_figuri);
                  end;
               end;
            inc(fcurent);
            end;
      if primaf=0 then
         begin
         { daca nu a intersectat nici o figura }
         { creeaza o noua figura care contine dreptunghiul curent }
         inc(numar_figuri);
         new(f[numar_figuri]);
         f[numar_figuri]^:=curent^;
         f[numar_figuri]^.urm:=nil;
         end;
      curent:=curent^.urm;
      end;
i:=1;
{ listeaza figurile }
while i<=numar_figuri do
    begin
    while (f[i]=nil) and (i<=numar_figuri) do inc(i);
    if f[i]<>nil then
       begin
       arie:=0;
       write(f[i]^.culoare,'  ');
       curent:=f[i];
       while curent<>nil do
             begin
             arie:=arie+(curent^.x2-curent^.x1)*(curent^.y2-curent^.y1);
             curent:=curent^.urm;
             end;
       writeln(arie);
       end;
    inc(i);
    end;
end.

             IOI. 11
Algoritm:
?????????????????????
Program:
type nume=string[15];
     matrice=array[1..100,1..100] of boolean;
     vector=array[1..100] of byte;
var legaturi:matrice;
    oras1,oras2,i,j,nr_maxim,nr_orase,nr_linii:byte;
    orase:array[1..100] of nume;
    solutie,lista:vector;
    parcurs:array[1..100] of boolean;
    directie:boolean;
    s:string[50];

function index(oras:nume):integer;
var i:integer;
    gasit:boolean;
begin
i:=1;
gasit:=false;
while (i<=nr_orase) and (not gasit) do
      begin
      if orase[i]=oras then gasit:=true
      else inc(i);
      end;
index:=i;
end;

procedure analizeaza(nr:integer);
var i:byte;
begin
if nr>nr_maxim then
   begin
   for i:=1 to nr do solutie[i]:=lista[i];
   nr_maxim:=nr;
   end;
end;

procedure ruta(oras,nr:byte);
var i:integer;
begin
lista[nr]:=oras;
if (oras=1) and (nr<>1) then analizeaza(nr)
else
    if not(parcurs[oras]) then
       begin
       if oras<>1 then parcurs[oras]:=true;
       if oras=nr_orase then directie:=FALSE;
       if directie then
          begin
          for i:=oras+1 to nr_orase do
              if (not(parcurs[i])) and (legaturi[oras,i]) then ruta(i,nr+1);
          end
       else
          for i:=1 to oras-1 do
              if (not(parcurs[i])) and (legaturi[oras,i]) then ruta(i,nr+1);
       if oras=nr_orase then directie:=TRUE;
       parcurs[oras]:=false;
       end;
end;

begin
assign(input,'input.i11');
reset(input);
assign(output,'output.i11');
rewrite(output);
readln(input,nr_orase,nr_linii);
nr_maxim:=1;
for i:=1 to nr_orase do
    begin
    parcurs[i]:=false;
    for j:=1 to nr_orase do legaturi[i,j]:=false;
    end;
directie:=true;
for i:=1 to nr_orase do readln(input,orase[i]);
for i:=1 to nr_linii do
    begin
    readln(input,s);
    oras1:=index(copy(s,1,pos(' ',s)-1));
    oras2:=index(copy(s,pos(' ',s)+1,length(s)-pos(' ',s)));
    legaturi[oras1,oras2]:=true;
    legaturi[oras2,oras1]:=true;
    end;
ruta(1,1);
writeln(nr_orase);
writeln(nr_maxim-1);
if nr_maxim>1 then
   for i:=1 to nr_maxim do writeln(orase[solutie[i]])
else writeln('NO MAP');
end.

             IOI. 12
Algoritm: Vom introduce datele problemei sub forma unei structuri nl[nuite, fiecare element avnd
forma:
              nivel   ascendent   valoare
Se introduce n plus un nod iniial care va avea forma   0   0   0
Aceast[ form[ permite un algoritm iterativ foarte simplu:
1. Pentru i:=1,n
   1.1. Pentru toate nodurile de pe nivelul i
           valoare(i):=valoare(i)+valoare(ascendent(i));
2. Se calculeaz[ valoarea maxim[ aflat[ n unul din nodurile de pe
   nivelul n; se tip[rete aceast[ valoare.
3. Stop 
Program:
uses crt;
var input:text;
    n,suma,sumamax,i,j:integer;
    g:array[1..100,1..100] of byte;

procedure parcurge(i,j:integer);
begin
suma:=suma+g[i,j];
if i<n then
   begin
   parcurge(i+1,j);
   parcurge(i+1,j+1);
   end
else if suma>sumamax then sumamax:=suma;
suma:=suma-g[i,j];
end;

begin
clrscr;
assign(input,'input.i12');
reset(input);
readln(input,n);
for i:=1 to n do
    begin
    for j:=1 to i do read(input,g[i,j]);
    readln(input);
    end;
suma:=0;
sumamax:=0;
parcurge(1,1);
writeln('Suma maxima este ',sumamax);
end.

                         IOI. 13
Algoritm:
???????????????????????
Program:
uses crt,graph;
type leg=^modul;
     modul=record
           x,y,tip:byte;
           urm:leg;
           end;
     legf=^figura;
     figura=record
            arie:integer;
            lista:leg;
            urm:legf;
            end;
     sol=record
         x,y:integer;
         c:char;
         end;
var fprima,fstart,fcurent:legf;
    max_arie,camere,a,b,i,j:integer;
    m,tmp:leg;
    solutie:sol;
    g:array[1..100,1..100] of integer;

procedure analizeaza(x1,y1,x2,y2:integer);
{ analizeaza casutele aflate la x1,y1 si x2,y2, care au un zid intre ele; daca
  fac parte din camere diferite, calculeaza aria maxima si propune solutia }
var gasit1,gasit2:boolean;
    arie:integer;
    f1,f2:legf;
begin
fcurent:=fstart;
gasit1:=false;
gasit2:=false;
arie:=0;
while not(gasit1 and gasit2) do
      begin
      tmp:=fcurent^.lista;
      while tmp<>nil do
            begin
            if (not gasit1) and (tmp^.x=x1) and (tmp^.y=y1) then
               begin
               gasit1:=true;
               arie:=arie+fcurent^.arie;
               f1:=fcurent;
               end
            else if (not gasit2) and (tmp^.x=x2) and (tmp^.y=y2) then
                 begin
                 gasit2:=true;
                 arie:=arie+fcurent^.arie;
                 f2:=fcurent;
                 end;
            if (tmp^.urm<>nil) and (tmp^.urm^.x>11) then
               readln;
            tmp:=tmp^.urm;
            end;
      fcurent:=fcurent^.urm;
      end;
if (f1<>f2) and (arie>max_arie) then
   begin
   max_arie:=arie;
   solutie.x:=x1;
   solutie.y:=y1;
   if x1>x2 then solutie.c:='W'
   else solutie.c:='S';
   end;
end;

function vecini(a,b:modul):boolean;
{ intoarce true daca doua module sunt legate (nu au perete intre ele) }
var r:boolean;
begin
r:=false;
if a.y=b.y then
   begin
   if (a.x=b.x-1) and ((a.tip and 4)<>4) then r:=true;
   if (a.x=b.x+1) and ((b.tip and 4)<>4) then r:=true;
   end
else if a.x=b.x then
        begin
        if (a.y=b.y-1) and ((b.tip and 2)<>2) then r:=true;
        if (a.y=b.y+1) and ((a.tip and 2)<>2) then r:=true;
        end;
vecini:=r;
end;

function in_figura(c:legf;m:leg):boolean;
{ intoarce true daca m are vecini in figura c }
var ct:leg;
begin
ct:=c^.lista;
while (ct<>nil) and (not vecini(m^,ct^)) do
      ct:=ct^.urm;
in_figura:=(ct<>nil);
end;

begin
clrscr;
assign(input,'input.i13');
{assign(output,'op');
rewrite(output);}
reset(input);
readln(input,a);
readln(input,b);
fstart:=nil;
for i:=1 to a do
    begin
    for j:=1 to b do
        begin
        new(m);
        read(input,m^.tip);
        m^.x:=j;
        m^.y:=i;
        m^.urm:=nil;
        fprima:=nil;
        fcurent:=fstart;
        g[j,i]:=m^.tip;
        while fcurent<>nil do
              begin
              if in_figura(fcurent,m) then
                 if fprima=nil then
                    begin
                    { daca este prima figura in care este intalnit atunci il
adauga la figura }
                    fprima:=fcurent;
                    tmp:=fprima^.lista;
                    while tmp^.urm<>nil do tmp:=tmp^.urm;
                    m^.urm:=fcurent^.lista;
                    fcurent^.lista:=m;
                    inc(fcurent^.arie);
                    end
                 else
                    begin
                    { daca nu este prima figura in care are vecini }
                    { adauga la fprima }
                    tmp^.urm:=fcurent^.lista;
                    while tmp^.urm<>nil do tmp:=tmp^.urm;
                    fprima^.arie:=fprima^.arie+fcurent^.arie;
                    { sterge fcurent }
                    fcurent^.lista:=nil;
                    fcurent^.arie:=0;
                    end;
              fcurent:=fcurent^.urm;
              end;
        if fprima=nil then
           begin
           { nu a fost adaugat la nici o figura }
           { creeaza o noua figura }
           new(fcurent);
           fcurent^.lista:=m;
           fcurent^.urm:=fstart;
           fstart:=fcurent;
           fstart^.arie:=1;
           end;
        end;
    readln(input);
    end;
max_arie:=0;
fcurent:=fstart;
camere:=0;
while fcurent<>nil do
      begin
      if fcurent^.arie>max_arie then max_arie:=fcurent^.arie;
      if fcurent^.arie>0 then inc(camere);
      fcurent:=fcurent^.urm;
      end;
writeln(' Camere : ',camere);
writeln(' Arie maxima : ',max_arie);
max_arie:=0;
for i:=1 to a do
    for j:=1 to b do
        begin
        { testarea se face numai pentru peretii din dreapta si jos, daca
exista }
        if (i<a) and (g[j,i] and 8=8) then analizeaza(j,i,j,i+1);
        if (j<b) and (g[j,i] and 4=4) then analizeaza(j,i,j+1,i);
        end;
writeln(' Poate fi eliminat peretele ',solutie.x,' ',solutie.y,' ',solutie.c);
end.

             IOI. 14
Algoritm:
?????????????
Program:
??????????????????????

                         IOI. 15
Algoritm:
??????????????????????
Program:
uses crt;
const transformare:array [1..9,1..3,1..3] of byte=
      (((1,1,0),(1,1,0),(0,0,0)),((1,1,1),(0,0,0),(0,0,0)),((0,1,1),
(0,1,1),(0,0,0)),((1,0,0),(1,0,0),(1,0,0)),((0,1,0),(1,1,1),(0,1,0)),((0,0,1),(0,0,1),(0,0,1)),((0,0,0),(1,1,0),(1,1,0)),((0,0,0),(0,0,0),(1,1,1)),((0,0,0),(0,1,1),(0,1,1)));
      valoare:array [1..9] of byte=(4,3,4,3,5,3,4,3,4);
type matrice=array [1..3,1..3] of byte;
     vector=array [1..9] of byte;
var x:matrice;
    lista,solutie:vector;
    i,j,sc,nminim,kk:byte;

procedure transforma(var ce:matrice;cum:byte);
{ transforma matricea ce cu transformarea nr. cum }
var i,j:integer;
begin
for i:=1 to 3 do for j:=1 to 3 do
    ce[i,j]:=(ce[i,j]+transformare[cum,i,j]) mod 4;
end;

function zero(g:matrice):boolean;
{ intoarce TRUE daca toate elementele matricii sunt 0 }
var i,j:byte;
    r:boolean;
begin
zero:=false;
for i:=1 to 3 do for j:=1 to 3 do
    begin
    r:=(g[i,j]<>0);
    if r then exit;
    end;
zero:=not r;
end;

procedure verifica(n:byte);
var i,j:byte;
    g:matrice;
begin
if n<nminim then
   begin
   for i:=1 to 3 do for j:=1 to 3 do g[i,j]:=x[i,j];
   for i:=1 to n do
       { aplica matricii de proba toate transformarile din lista }
       transforma(g,lista[i]);
   if zero(g) then
      begin
      nminim:=n;
      for i:=1 to n do solutie[i]:=lista[i];
      end;
   end;
end;

procedure complementar(g:matrice);
var s,i,j:byte;
begin
sc:=0;
for i:=1 to 3 do for j:=1 to 3 do sc:=sc+(4-g[i,j]) mod 4;
end;
procedure calc(suma:integer;index:byte);
var i:integer;
begin
if suma<>sc+kk*4 then
   begin
   for i:=1 to 9 do
       begin
       lista[index]:=i;
       if valoare[i]+suma<=sc+kk*4 then
          calc(suma+valoare[i],index+1);
       end;
   end
else verifica(index-1);
end;

begin
clrscr;
assign(input,'input.i15');
reset(input);
for i:=1 to 3 do
    begin
    for j:=1 to 3 do read(input,x[i,j]);
    readln(input);
    end;
close(input);
for i:=1 to 9 do solutie[i]:=0;
complementar(x); { calculeaza suma complementara }
nminim:=9;
kk:=0;
repeat
      calc(0,1);
      inc(kk);
      writeln(kk);
until (nminim<>9) or (kk>9);
if solutie[1]<>0 then for i:=1 to nminim do write(solutie[i])
else writeln('Nu exista solutie.');
end.

             IOI. 16
Algoritm:
???????????????????
Program:
uses crt;
var a:array[1..300] of byte;
    folosit:array[1..300] of boolean;
    solutie,vector:array[1..100] of integer;
    i,tminim,nr_autobuze:integer;

function verifica(t,n:integer):boolean;
var i,j:integer;
    gasit:boolean;
begin
gasit:=true;
i:=a[t]; { i este timpul opririi t }
j:=1;
while (i<=59) and gasit do
      begin
      { daca nu exista oprirea cu timpul i }
      gasit:=false;
      while (j<=nr_autobuze) and (not gasit) do
            if (a[j]=i) and (not folosit[j]) then gasit:=true
            else inc(j);
      i:=i+n;
      end;
{ anunta daca au fost gasite toate opririle }
verifica:=gasit;
end;

function opriri:integer;
{ Intoarce numarul primei opriri nestudiate sau 0 daca nu exista }
var i:integer;
begin
i:=1;
while (folosit[i]) and (i<=nr_autobuze) do i:=i+1;
if i>nr_autobuze then opriri:=0
else opriri:=i;
end;

procedure marcheaza(t:integer);
var i:integer;
begin
tminim:=t;
for i:=1 to t do solutie[i]:=vector[i];
end;

procedure cauta(t:integer);
var n,i,j:integer;
begin
n:=1;
while (n<=30) do
      begin
      vector[t]:=n;
      { daca traseul cu prima oprire la momentul a[t] si perioada n verifica
}
      if verifica(t,n) then
         begin
         { ii marcheaza opririle ca folosite }
         i:=a[t];
         j:=t;
         while i<=59 do
               begin
               while (j<=nr_autobuze) and (a[j]<>i) do inc(j);
               if j<=nr_autobuze then
               if not folosit[j] then
                  begin
                  folosit[j]:=true;
                  i:=i+n;
                  end
               else j:=j+1;
               end;
         { daca mai exista opriri }
         j:=opriri;
         { repeta procedura pentru urmatoarea oprire }
         if j<>0 then cauta(j)
         { altfel marcheaza solutia }
         else if t<tminim then marcheaza(t);
         { demarcheaza opririle }
         i:=a[t];
         j:=t;
         while i<=59 do
               begin
               while (j<=nr_autobuze) and (a[j]<>i) and (a[j]<=i) do inc(j);
               if folosit[j] then
                  begin
                  folosit[j]:=false;
                  i:=i+n;
                  end
               else j:=j+1;
               end;
         end;
      inc(n);
      end;
end;

begin
clrscr;
assign(input,'input.i16');
reset(input);
readln(input,nr_autobuze);
for i:=1 to nr_autobuze do
    begin
    read(a[i]);
    folosit[i]:=false;
    end;
tminim:=17;
cauta(1);
for i:=1 to tminim do writeln(a[i],' ',solutie[i]);
close(input);
end.

             IOI. 17
Algoritm:
              Din fiierul de intrare se citesc n ordine n (num[rul de sectoare), mm (cel mai mic num[r ce
trebuie realizat) i k (valoarea minim[ a numerelor ce pot fi nscrise n sectoare).
               Construiesc lista sm avnd nsm=n(n-1)+1 elemente. Pentru fiecare i=1,...,n-1, valoarea
i i succesiunea de i sectoare ce ncepe de pe poziia kk vor fi plasate n list[ pe poziia(i-1)n+kk.
Pe poziia nsm va fi plasat n i succesiunea 1,2,...,n de sectoare consecutive.
               Este evident c[ pentru o etichetare dat[ a sectoarelor, parcurgerea listei sm va permite
determinarea tuturor numerelor realizabile. Cerinele problemei constau ns[ n a determina o
etichetare optim[ a sectoarelor.
               O etichetare a sectoarelor va fi un vector cu n componente (tipul tvec). Soluia problemei va
fi un vector solv de descrieri ale etichet[rilor.
               Prin ms este notat[ valoarea maxim[ pentru care exist[ o etichetare astfel nct numerele
mm,mm+1,...,ms s[ fie realizabile. Vom pleca cu ms=0, valoare care nu se va modifica dac[ nu
exist[ soluii (cazul mm<k).
               Orice etichetare vec a sectoarelor va avea cea mai mic[ valoare pe poziia 1. Pentru fiecare
vector vec=(kmin,0,...,0), unde kmin=k,k+1,...,1+mm div 2 se apeleaz[ procedura
bactracking recursiv[ bk prin bk(mm).
               Procedura bk avnd parametrul m urm[rete s[ completeze unele dintre poziiile libere ale lui
vec astfel nct valoarea m s[ fie realizabil[. Consider[m pe rnd elementele listei sm. Se verific[
nti dac[ valoarea m este deja realizabil[ pe baza succesiunii de sectoare ce constituie elementul
curent al listei. In caz afirmativ se apelaz[ bk(m+1), ncercndu-se de a-l face i pe m+1 realizabil.
In caz contrar: dac[ mai exist[ sectoare neetichetate i dac[ exist[ un element din lista sm (o
succesiune de sectoare) astfel nct prin completarea cu valoarea minim[ kmin a sectoarelor libere ale
succesiunii considerate se obine o sum[ ce nu dep[ete m, atunci este apelat[ procedura b, care
ncearc[ s[ completeze sectoarele libere din succesiune astfel nct m s[ devin[ realizabil (dac[
procedura b va reui n aceast[ ncercare, ea va efectua apelul bk(m+1)0, prin care se caut[ a-l face
i pe m+1 realizabil).
             Dac[ procedura bk ajunge s[ fie apelat[ pentru o valoare m cu m-1ms, atunci:
   - dac[ m-1>ms, atunci optimul a fost mbun[t[it i atunci vechiul coninut al lui sol este anulat
i este apelat[ procedura adauga;
   - dac[ m-1=ms, atunci optimul mai poate fi atins nc[ ntr-un mod i este apelat[ procedura
adauga.
               Procedura adauga pleac[ de la un vector soluie, compleaeaz[ poziiile sale neocupate cu
mm i dac[ vectorul astfel obinut nu se afl[ n solv l adaug[ lui solv.
Program:
?????????????????????

               IOI. 18
??????????


------------------------------
IOI 41 (Rute aeriene)
Soluie:
uses crt;
type rt=record
        start,ends:byte;
        end;
var r:array[1..100] of rt;
    parcurs:array[1..100] of boolean;
    solutie,lista:array[1..100] of byte;
    i,j,nr_rute,nr_orase:byte;
    d:array[1..10,1..10] of integer;
    d_min:integer;

procedure verifica(nr:integer);
{ verifica daca ruta curenta este cea mai scurta }
var i,oras1:byte;
    distanta:integer;
begin
if (lista[1]=2) and (lista[2]=4) and (lista[3]=3) and (lista[4]=1) and
(lista[5]=5) then
   delay(1);
oras1:=1;
distanta:=0;
for i:=1 to nr do
    begin
   
distanta:=distanta+d[oras1,r[lista[i]].start]+d[r[lista[i]].start,r[lista[i]].ends];
    oras1:=r[lista[i]].ends;
    end;
if r[lista[nr]].ends<>1 then distanta:=distanta+d[1,r[lista[nr]].ends];
if distanta<d_min then
   begin
   d_min:=distanta;
   for i:=1 to nr_rute do solutie[i]:=lista[i];
   end;
end;

procedure traseu(ruta,nr:byte);
var i:byte;
begin
parcurs[ruta]:=true;
lista[nr]:=ruta;
if nr=nr_rute then verifica(nr)
else for i:=1 to nr_rute do
         if (not parcurs[i]) then traseu(i,nr+1);
parcurs[ruta]:=false;
end;

begin
clrscr;
assign(input,'input.i19');
assign(output,'output.i19');
reset(input);
rewrite(output);
readln(nr_orase);
for i:=1 to nr_orase do
    begin
    for j:=1 to nr_orase do read(d[i,j]);
    readln;
    end;
readln(nr_rute);
for i:=1 to nr_rute do
    begin
    readln(r[i].start,r[i].ends);
    parcurs[i]:=false;
    end;
d_min:=MAXINT;
for i:=1 to nr_rute do traseu(i,1);
writeln(d_min);
if r[solutie[1]].start<>1 then write('1 ');
r[solutie[nr_rute+1]].start:=2;
for i:=1 to nr_rute do
    begin
    write(r[solutie[i]].start,' ');
    if r[solutie[i]].ends<>r[solutie[i+1]].start then
       write(r[solutie[i]].ends,' ');
    end;
if r[solutie[nr_rute]].ends<>1 then writeln('1')
end.
----------------------------------
IOI 42:
Soluie:
uses crt;
type punct=record
           x,y:integer;
           end;

var i,n,a:integer;
    curent,final,next:punct;
    ob:array[1..30] of punct;

function intersect(o:punct):integer;
var r,a,b:integer;
    m,n:real;
begin
r:=0;
b:=o.y;
a:=o.x;
m:=(final.y-curent.y)/(final.x-curent.x);
n:=final.y-m*final.x;
if (m*a+n>=b) and (m*a+n<=b+5) then r:=4
else if ((b-n)/m>=a) and ((b-n)/m<=a+5) then r:=2;
if (b=curent.y) or (b+5=curent.y) then r:=0;
intersect:=r;
end;

begin
clrscr;
writeln('0 0');
assign(input,'input.i20');
reset(input);
readln(input,n);
for i:=1 to n do
    begin
    readln(ob[i].x,ob[i].y);
    end;
close(input);
final.x:=100;
final.y:=100;
curent.x:=0;
curent.y:=0;
while ((curent.x<>final.x) or (curent.y<>final.y)) do
      begin
      next:=final;
      for i:=1 to n do
          begin
          if (ob[i].x>=curent.x) and (ob[i].x<=next.x) then
             begin
             a:=intersect(ob[i]);
             if a<>0 then
             if a=1 then
                begin
                next.x:=ob[i].x;
                next.y:=ob[i].y;
                end
             else if a=2 then
                begin
                next.x:=ob[i].x+5;
                next.y:=ob[i].y;
                end
             else if a=3 then
                begin
                next.x:=ob[i].x+5;
                next.y:=ob[i].y+5;
                end
             else if a=4 then
                begin
                next.x:=ob[i].x;
                next.y:=ob[i].y+5;
                end;
             end;
          end;
      curent:=next;
      writeln(curent.x,' ',curent.y);
      end;
end.
---------------------------------
